学步园

以下是n的方法

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Title: Longest_Up.java
 * @Package
 * @Description: TODO
 * @author nutc
 * @date 2013-9-8 下午7:16:34
 * @version V1.0
 */
public class Longest_Up {

	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);
		int n;
		while (sc.hasNext()) {
			n = sc.nextInt();
			int[] now = new int[n];
			for (int i = 0; i < n; i++)
				now[i] = sc.nextInt();
			System.out.println(find1(now));
		}
	}

	// public static int find(int[] num){
	// if(num==null) return 0;
	//
	// int big=1;
	//
	// int min = num[num.length-1];
	// for(int i=num.length-2;i>=0;i--){
	// if(num[i]<min){
	// min=num[i];
	// big++;
	// }
	// }
	// return big;
	// }

	public static int find1(int[] num) {
		if (num == null)
			return 0;

		int big = 1;
		int[] max = new int[num.length];
		int[] now = new int[num.length];  //非常重要，记录在自己前面的比自己小的最大值！
		Arrays.fill(max, 1);
		Arrays.fill(now, -1);
		for (int i = 1; i < num.length; i++) {
			int j = i - 1;
			while (j >= 0 && num[j] >= num[i]) {
				j = now[j];
			}
			now[i] = j;
			if (j >= 0) {
				max[i] = max[j] + 1;
				if (max[i] > big)
					big = max[i];
			}
//			System.out.println(i + " " + j);
		}
		return big;
	}

}



以下是n^2的方法
package Array;  

import java.util.Arrays;

/** 
 * @Title: LongestIncrease.java 
 * @Package Array 
 * @Description: TODO
 * @author nutc
 * @date 2013-8-28 下午2:28:11 
 * @version V1.0 
 */
public class LongestIncrease {
	
	public static void main(String args[]){
		int []  a = {1,-1,2,-3,4,-5,6,-7};
		System.out.println(find(a));
	}
	
	public static int find(int[] num){
		
		int longset [] = new int[num.length];
		Arrays.fill(longset, 1);
		
	    int max = 1;
	    
	    for(int i=1;i<num.length;i++){
	    	
	    	for(int j=i-1;j>=0;j--){
	    		if(num[j]<num[i]){
	    			num[i]+=num[j]+1;
	    			if(num[i]>max)
	    				max = num[i];
	    			break;  //要记得break！  不然全部都要循环下了...
	    		}
	    	}
	    }
	    return max;
	}

}