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

Input : arr[] = {1 6 2 4 3} Output : 3

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;
    }
}