# Solution For Non Decreasing Subsequences

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, , the length of the non-decreasing subsequence ending at the first index would be 1.

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

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

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

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

For the sixth element, , it forms a non-decreasing subsequence with , . 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, , it does not form a non-decreasing subsequence with , , , . 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:

`python class Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) dp = *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).

## Step by Step Implementation For Non Decreasing Subsequences

```class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0;

for(int x : nums) {
int i = Arrays.binarySearch(dp, 0, len, x);
if(i < 0) i = -(i + 1);
dp[i] = x;
if(i == len) len++;
}

return len;
}
}```
```def findSubsequences(nums):
res = []
for i in range(len(nums)):
if i == 0 or nums[i] >= nums[i-1]:
# start a new non-decreasing subsequence
curr = [nums[i]]
for j in range(i+1, len(nums)):
if nums[j] >= curr[-1]:
# extend the current subsequence
curr.append(nums[j])
res.append(curr[:])
# backtrack to find other subsequences
findSubsequences(nums[i+1:], curr, res)
return res```
```var findSubsequences = function(nums) {
var res = [];
var dfs = function(index, path) {
if (path.length >= 2) {
res.push(path.slice());
}
var hash = {};
for (var i = index; i < nums.length; i++) {
if (hash[nums[i]]) {
continue;
}
if (path.length === 0 || path[path.length - 1] <= nums[i]) {
hash[nums[i]] = true;
path.push(nums[i]);
dfs(i + 1, path);
path.pop();
}
}
}
dfs(0, []);
return res;
};```
```class Solution {
public:
int findNumberOfLIS(vector& nums) {
int n = nums.size(), res = 0, max_len = 0;
vector len(n, 1), cnt(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
if (len[i] == len[j] + 1) {
cnt[i] += cnt[j];
}
else if (len[i] < len[j] + 1) {
len[i] = len[j] + 1;
cnt[i] = cnt[j];
}
}
}
if (max_len == len[i]) {
res += cnt[i];
}
else if (max_len < len[i]) {
max_len = len[i];
res = cnt[i];
}
}
return res;
}
};```
```public class Solution {
public int MinNumberOfSubsequences(int[] nums) {
// Corner case
if (nums == null || nums.Length == 0) {
return 0;
}

// DP array, dp[i] represents the minimum number of subsequences
// needed to make nums[0..i] non-decreasing
int[] dp = new int[nums.Length];
dp = 1;

// Iterate through the array
for (int i = 1; i < nums.Length; i++) {
// If nums[i] is greater than the previous element,
// then we can use it to form a new subsequence
if (nums[i] >= nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
} else {
// Otherwise, we can't use nums[i] to form a new subsequence,
// but we can still use the previous subsequences
dp[i] = dp[i - 1];
}
}

// The minimum number of subsequences needed is the last element
// in the DP array
return dp[nums.Length - 1];
}
}```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]