Skip to content
AI360Xpert
Back to 1-D Dynamic Programming
Medium

Longest Increasing Subsequence

Given an integer array `nums`, return the length of the longest strictly increasing subsequence. A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Examples

Input:nums = [10,9,2,5,3,7,101,18]
Output:4
The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Input:nums = [0,1,0,3,2,3]
Output:4
The longest increasing subsequence is [0,1,2,3].
Input:nums = [7,7,7,7,7,7,7]
Output:1
The subsequence must be strictly increasing, so the longest one is just a single 7.

Constraints

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4

Dynamic Programming

Approach

We use a DP array where `dp[i]` represents the length of the longest increasing subsequence ending at index `i`. We initialize all elements of `dp` to 1 because the minimum LIS ending at any element is just the element itself. For each element `nums[i]`, we iterate through all preceding elements `nums[j]` (where `j < i`). If `nums[i] > nums[j]`, it means we can append `nums[i]` to the LIS ending at `nums[j]`. So we update `dp[i] = max(dp[i], 1 + dp[j])`. The final result is the maximum value in the `dp` array.

Complexity Analysis

Time Complexity
O(n^2)
Space Complexity
O(n)

Time complexity is O(n^2) due to the nested loops. A more optimized O(n log n) solution exists using Binary Search and a separate array, but O(n^2) DP is standard and sufficient.

Solution.java
class Solution {    public int lengthOfLIS(int[] nums) {        if (nums == null || nums.length == 0) return 0;                int n = nums.length;        int[] dp = new int[n];        Arrays.fill(dp, 1); // Minimum length is 1 (the element itself)                int maxLen = 1;                for (int i = 1; i < n; i++) {            for (int j = 0; j < i; j++) {                // If strictly increasing                if (nums[i] > nums[j]) {                    dp[i] = Math.max(dp[i], dp[j] + 1);                }            }            maxLen = Math.max(maxLen, dp[i]);        }                return maxLen;    }}