単調に増加するサブアレイの数を見つける

Question

配列を考えれば、その配列内に単調増加するサブアレイがいくつあるか調べる必要がありますか？

たとえば[0,1,3,1,2]は[0,1,3]と[1,2]の2つの単調なサブアレイを持ちます。

public class SUB_ARRAY { 
    public static void main(String a[]){ 
     int[] x = new int[6]; 
     x[0]=1; 
     x[1]=2; 
     x[2]=3; 
     x[3]=6; 
     x[4]=9; 
     x[5]=10; 
     ArrayList<Object> arraylist = new ArrayList<Object>(); 
     HashSet list = new HashSet(); 
     for (int i=0; i< (x.length -1); i++){ 
      if (x[i+1]> x[i]){ 
       list.add(x[i]); 
       list.add(x[i+1]); 

      } else if (x[i+1] < x[i] || x[i+1]==x[i]) { 
       arraylist.add(list.clone());  
       list.clear();  
      } 
     }  
     System.out.println(arraylist.size()); 

    }  
} 

出力は、0（1ではなく）です。

だから私は間違っていますか？

Answer 1

この解決策を確認してください。現在はカウンターが表示されますが、サブアレイは印刷されます。続行サブアレイだけが必要な場合は、簡単に変更することができます。
私はHashSetとArrayListの両方を使用して一時的なデータをカウンタとして保存することはしません。

import java.util.ArrayList; 
public class SUB_ARRAY{ 
    public static int SUBARRAY_MINIMUM_LENGTH = 2; 
    public static void main(String a[]){ 
     ArrayList<Integer> x = new ArrayList<Integer>(); 
     x.add(5); 
     x.add(0); 
     x.add(1); 
     x.add(3); 
     x.add(4); 
     x.add(2); 
     x.add(3); 
     x.add(6); 
     x.add(1); 
     x.add(0); 
     x.add(4); 
     int monoton = 0; 
     int changed = -1; 
     System.out.println("Initial array: " + x.toString()); 
     for (int i=0; i< x.size() -1; ++i){ 
      if (x.get(i+1) > x.get(i)){ 
       if (changed > -1){ 
        for (int j = changed; j <i+2; ++j){ 
         monoton += checkSubArray(x, j, i+2);; 
        } 
       } 
       else{ 
        System.out.println("New monoton subarray start index: " + i + " value: " + x.get(i)); 
        changed = i; 
        monoton += checkSubArray(x, changed, i+2); 
       } 
      } 
      else if (changed > -1){ 
       changed = -1; 
      } 
     }  
     System.out.println("Monoton count: " + monoton); 
    }  

    private static int checkSubArray(ArrayList<Integer> x, int start, int end) 
    { 
     if (end-start < SUBARRAY_MINIMUM_LENGTH){ 
      return 0; 
     } 
     for (int subi = start; subi < end; ++subi){ 
      System.out.print(" " + x.get(subi)); 
     } 
     System.out.println(); 
     return 1; 
    } 
} 

出力は次の

 
Initial array: [5, 0, 1, 3, 4, 2, 3, 6, 1, 0, 4] 
New monoton subarray start index: 1 value: 0 
0 1 
0 1 3 
1 3 
0 1 3 4 
1 3 4 
3 4 
New monoton subarray start index: 5 value: 2 
2 3 
2 3 6 
3 6 
New monoton subarray start index: 9 value: 0 
0 4 
Monoton count: 10