> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/minimum-number-of-increasing-subsequences.md).

# Minimum number of increasing subsequences

Given an array of integers of size N, you have to divide it into the minimum number of “strictly increasing subsequences”\
For example: let the sequence be {1, 3, 2, 4}, then the answer would be 2. In this case, the first increasing sequence would be {1, 3, 4} and the second would be {2}.

Examples:

> Input : arr\[] = {1 3 2 4}\
> Output: 2\
> There are two increasing subsequences {1, 3, 4} and {2}
>
> Input : arr\[] = {4 3 2 1}\
> Output : 4
>
> Input : arr\[] = {1 2 3 4}\
> Output : 1\ <br>
>
> Input : arr\[] = {1 6 2 4 3}\
> Output : 3

```java
class Solution {
    public int minIncSubsequences(int arr[], int n) {
        // Ans -> Max lenth of longest decreasing subsequence
        int[] dp = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            // base case
            dp[i] = 1;
            for (int j = 0; j < i; j++)
                if (arr[j] > arr[i])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
```