Submission #34258

---

Source Code Expand

import java.util.*;

public class Main{
	public static int solve(int[] data){
		boolean[] check = new boolean[data.length];
		int count = 0;
		for(int i = 0; i < data.length; i++){
			if( check[i] ){
				continue;
			}
			count++;
			Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
			List<Integer> temp = new ArrayList<Integer>();
			temp.add(i);
			map.put(1, temp);
			for(int j = i+1; j < data.length; j++){
				if( check[j] ){
					continue;
				}
				if( data[j] <= data[i] ){
					int t = map.size();
					for(int k = t-1; k >= 0; k--){
						List<Integer> list = new ArrayList<Integer>(map.get(k+1));
		//				System.out.println("list " + list);
						if( data[list.get(list.size()-1)] >= data[j] ){
							if( map.get(k+2) == null ){
			//					System.out.println("aha" + j);
								list.add(j);
								map.put(k+2, list);
			//					System.out.println(map);
							} else if( data[map.get(k+2).get(map.get(k+2).size()-1)] > data[j] ){
								list.add(j);
								map.put(k+2, list);
							}
						}
					}
		//			System.out.println(map);
				}
			}
//			System.out.println(map);
			for(Integer x : map.get(map.size())){
				check[x] = true;
			}
		}
		return count;
	}		
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		int n = stdIn.nextInt();
		int[] data = new int[n];
		for(int i = 0; i < n; i++){
			data[i] = stdIn.nextInt();
		}
		System.out.println(solve(data));
	}
}

Submission Info

Judge Result