O(n^2) sol with DP - using an optimization


  • 1

    The optimization lies in the loop check.

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

Log in to reply
 

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