Classic JAVA O(n*n) Solution


  • 0
    Y

    The idea is to find the max length of subsequence that ends with index i.
    So max[i] = max[j = 0..i-1] + 1 (when nums[i] > nums[j]); Here is the code:

    public class Solution {
        public int lengthOfLIS(int[] nums) {
            int dp[] = new int[nums.length], max = 0;
            for (int i = 0; i < nums.length; ++i) {
                max = 1;
                for (int j = 0; j < i; ++j) {
                    if (nums[i] > nums[j]) {
                        max = Math.max(max, dp[j] + 1);
                    }
                }
                dp[i] = max;
            }
            for (int i = 0; i < dp.length; ++i) {
                max = Math.max(max, dp[i]);
            }
            return max;
        }
    }
    

    Thanks.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.