最长递增子序列

//这个题其实找的是索引
import java.util.*;

public class AscentSequence {
    public int findLongest(int[] A, int n) {
        // write code here
        //循环每个数字
        int max;
        int count;
        int maxLen=1;
        for(int i=0;i<A.length-1;i++){
            count=1;
            max=A[i];
            for(int j=i+1;j<A.length;j++){
                if(A[j]>max){
                	count++;
                	max=A[j];
            	}
            }
            maxLen=Math.max(count,maxLen);
        }
        return maxLen;
    }
}
为何只通过20%

//找到了原因。以下动态规划通过全部
/*
要求长度为i以前的序列，以i-1结尾的是多少呢？dp[i]表示A[i-1]以前的子序列
*/

/*
 * 203,39,186 
 * dp0:0
   dp1:1
   dp2:1
   dp3:1显然应该是2.但是如果和前边最大的比较，还是1
 * */
/*
 * dp[i]表示以第i个元素结尾(A[i])递增子序列个数
 * 初始化dp[i]=0;
 * dp[i]=max(dp[j])+1 (j=0,1,2..i-1)where A[i]>A[j]
 * */
/*
要求长度为i以前的序列，以i-1结尾的是多少呢？dp[i]表示A[i-1]以前的子序列
*/
import java.util.*;

public class AscentSequence {
    public int findLongest(int[] A, int n) {
        int[] dp = new int[n];
        for(int i=0;i<A.length;i++){
        	dp[i]=1;
        }
        int max=1;
        for(int i=1;i<A.length;i++){
        	for(int j=0;j<i;j++){
        		if(A[i]>A[j]){
        			dp[i]=Math.max(dp[j]+1,dp[i]);//取的是dp[j]+1中的最大的
        		}
        	}
        	max = Math.max(max, dp[i]);
        }       
        return max;
    }
}

import java.util.*;

public class AscentSequence {
    public int findLongest(int[] A, int n) {
        // write code here
        int[] dp=new int[n];
        int[] ends=new int[n];
        ends[0]=A[0];
        dp[0]=1;
        int max=1;
        int r=0,right=0,l=0,m=0;
        for(int i=1;i<n;i++){
            l=0;
            r=right;
            while(l<=r){
                m=(l+r)/2;
                if(A[i]>ends[m]){
                    l=m+1;
                }else{
                    r=m-1;
                }
            }
            //没明白
            right=Math.max(l,right);
            ends[l]=A[i];
            dp[i]=l+1;
            max=Math.max(dp[i],max);
        }
        return max;
    }
}

import java.util.*;
public class AscentSequence {
    public int findLongest(int[] A, int n) {
		int[] dp = new int[n];
		Arrays.fill(dp, 1);
		for (int i = 1; i < dp.length; i ++ ) {
			int max = 0;
			for (int j = i - 1; j >= 0; j -- ) {
				if(A[i] > A[j] && max < dp[j]) {
					max = dp[j];
					dp[i] = dp[j] + 1;
				}
			}
		}
		int res = 0;
		for (int i:dp) {
			res = res > i ? res : i;
		}
		return res;
	}
}

import java.util.*;

public class AscentSequence {
    public int findLongest(int[] A, int n) {
        // write code here
        int[] dp = new int[n];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; ++i) {
            if (i == 0) {
                dp[i] = 1;
            } else {
                dp[i] = 1;
                for (int j = i - 1; j >= 0; --j) {
                    if (A[j] < A[i]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}