[Java] Super Brief explanation to save ur life.


  • 0

    ~Why it's a DP problem?~

    dp[i] holds the smallest number tan have LIS with length i+1.

    public int lengthOfLIS(int[] nums) {
            if (nums == null || nums.length < 1) return 0;
            int[] dp = new int[nums.length];
            int len = 0;
            for (int num : nums) {
                int i = Arrays.binarySearch(dp, 0, len, num);
                // if not found, return -(termination index + 1),
                // where you should insert the number.
                if (i < 0) {
                    i = -(i + 1);
                    dp[i] = num;
                    if (i == len) len++;
                }
                // if found, do nothing.
            }
            return len;
        }
    

    p.s: I do hate people using titles such as easy explanation!!!!!, best submission, best solution. That's why I use Super Brief to satirize on them. LoL.


Log in to reply
 

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