Given an array A[0]...A[n-1] of integers, find out the length of the longest ascending subsequence.

Assumptions

• A is not null

Examples
Input: A = {5, 2, 6, 3, 4, 7, 5}
Output: 4
Because [2, 3, 4, 5] is the longest ascending subsequence.

Subsequence not necessary continuous

subarray must continuous

solution 1 :

1. 求longest ， 一般会用到DP， best first search。 这个问题符合大一号问题可以同过小一号问题解决， 所以用DP
2. 1 dimension DP, 同样的weight，符合linear 回头看的原则

dp[i] indicates longest subsequence from subarray array[0 - i]

base case: dp[0] = 1

induction rule: dp[i] = max(dp[i], 1 + dp[j]) ( 0<= j < i, array[j] < array[i])

Time complexity O(n^2), space complexity O(n)

public class LongestSubSequence {
    public int longest(int[] array) {
        if (array == null) {
            return 0;
        }
        int globalmax = 0;
        int[] dp = new int[array.length];
        for(int i = 0; i < array.length; i++) {
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if (array[j] < array[i]) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
            globalmax = Math.max(globalmax,dp[i]);
        }
        return globalmax;
    }
}

Solution 2 : O(n log n)