Non Decreasing Subsequences - Leetcode Solution

Problem Statement:

Given an integer array nums, return the length of the longest non-decreasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest non-decreasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3] Output: 4

Solution:

The problem is about finding the length of the longest non-decreasing subsequence. A non-decreasing subsequence is a subsequence in which the elements are in increasing order. Therefore, the subsequence could be in any order, just that the elements should be in increasing order.

A simple approach would be to find all the subsequences of the given array and check which ones are in increasing order. Then, we would take the longest of these increasing subsequences.

However, this approach would take an exponential time which would not be efficient.

The Dynamic Programming approach is the best approach for such problems. For this problem, we need to consider the length of non-decreasing subsequences ending at each index.

Consider the given array nums = [10,9,2,5,3,7,101,18]

For the first element, [10], the length of the non-decreasing subsequence ending at the first index would be 1.

For the second element, [9], it does not form a non-decreasing subsequence with [10]. Therefore the length of the non-decreasing subsequence ending at the second index would be 1.

For the third element, [2], it does not form a non-decreasing subsequence with [9] and [10]. Therefore the length of the non-decreasing subsequence ending at the third index would be 1.

For the fourth element, [5], it forms a non-decreasing subsequence with [2]. Therefore the length of the non-decreasing subsequence ending at the fourth index would be 2.

For the fifth element, [3], it does not form a non-decreasing subsequence with [2]. Therefore the length of the non-decreasing subsequence ending at the fifth index would be 1.

For the sixth element, [7], it forms a non-decreasing subsequence with [2], [5]. Therefore the length of the non-decreasing subsequence ending at the sixth index would be 3.

For the seventh element, [10,9,2,5,3,7,101], we can see that the non-decreasing subsequence would be [2,5,7,101]. Therefore the length of the non-decreasing subsequence ending at the seventh index would be 4.

For the eighth element, [18], it does not form a non-decreasing subsequence with [2], [5], [7], [101]. Therefore the length of the non-decreasing subsequence ending at the eighth index would be 1.

Therefore, the length of the longest non-decreasing subsequence would be the maximum length among all non-decreasing subsequences ending at each index.

The code for the same would be:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1]*n # Initializing all indices as 1
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)

The time complexity of the solution would be O(n^2) and the space complexity would be O(n).

1