1. Problem Statement

Given an array arr[] of size n, we need to divide its elements into:

Each array element can be used in at most one of these subsequences. Some elements may be left unused.

Our goal is to minimize the number of unused elements.

Equivalently:

Maximize the number of elements that can be included in the two subsequences.

Finally:

Code
Answer = n - maximum number of selected elements

2. Example

Consider:

Code
arr = [7, 8, 1, 2, 4, 6, 3, 5, 2, 1, 8, 7]

One possible solution is:

Code
Increasing: [1, 2, 4, 5, 8]

Decreasing: [7, 6, 3, 2, 1]

Total selected:

Code
5 + 5 = 10

Array size:

Code
n = 12

Therefore:

Code
Unused = 12 - 10
       = 2

So the answer is:

Code
2

3. Why Is This a Dynamic Programming Problem?

When we process the array from left to right, every element has three possibilities.

Option 1 — Put It in Increasing Subsequence

For example:

Code
Increasing = [1, 2, 4]
Current element = 5

Since:

Code
5 > 4

we can add 5.

Option 2 — Put It in Decreasing Subsequence

For example:

Code
Decreasing = [8, 6, 3]
Current element = 2

Since:

Code
2 < 3

we can add 2.

Option 3 — Don't Use It

The current element can simply be ignored.

Therefore, at every element we have up to three choices.

The difficulty is that we need to remember the last element of both subsequences. That's where DP comes in.

4. DP State

We use:

Java
dp[i][j]

where:

The value stored in dp[i][j] is:

The maximum number of elements selected so far.

For example:

Code
dp[4][7]

means:

Code
Increasing subsequence ends at arr[4]
Decreasing subsequence ends at arr[7]

and the value tells us how many elements have been selected.

5. What About an Empty Subsequence?

Initially, both subsequences are empty.

There is no index representing an empty subsequence. So we use:

Java
n

as a special/virtual index.

Therefore:

Java
dp[n][n] = 0;

means:

Code
Increasing subsequence = empty
Decreasing subsequence = empty
Selected elements = 0

This is a very useful DP technique: using an extra index as a sentinel.

6. Processing Each Element

Suppose the current element is:

Java
arr[k]

We examine every possible DP state:

Java
dp[i][j]

There are three transitions.

7. Transition 1 — Skip the Element

The easiest case is to leave arr[k] unused.

The state doesn't change:

Java
next[i][j] = Math.max(next[i][j], selected);

For example:

Code
Before:
Increasing ends at 4
Decreasing ends at 7

Current element = 10

We may decide not to use 10.

So the state remains unchanged.

8. Transition 2 — Add to Increasing Subsequence

The increasing subsequence must be strictly increasing.

Therefore:

Java
arr[k] > arr[i]

must be true.

There is one special case:

Java
i == n

which means the increasing subsequence is currently empty.

So the condition is:

Java
if (i == n || arr[k] > arr[i])

If valid, we update:

Java
next[k][j] = Math.max(
    next[k][j],
    selected + 1
);

Why next[k][j]?

Because after adding arr[k], the last element of the increasing subsequence becomes k.

9. Transition 3 — Add to Decreasing Subsequence

Similarly, the decreasing subsequence must be strictly decreasing.

Therefore:

Java
arr[k] < arr[j]

must be true.

Again, if:

Java
j == n

the decreasing subsequence is empty.

So:

Java
if (j == n || arr[k] < arr[j])

If valid:

Java
next[i][k] = Math.max(
    next[i][k],
    selected + 1
);

The increasing subsequence's last index remains i.

The decreasing subsequence's last index becomes k.

10. Why Do We Need next[][]?

This is an important part of the implementation.

Suppose we are processing:

Java
arr[k]

We should not immediately modify dp.

Instead, we calculate all possibilities in:

Java
next

Then after processing the current element:

Java
dp = next;

This means:

Code
dp     → states before processing arr[k]
next   → states after processing arr[k]

This prevents the same element from accidentally being used multiple times during the same iteration.

11. Complete Java Code

Java
class Solution {
    public int minCount(int[] arr) {
        int n = arr.length;

        // dp[i][j]:
        // i = last index of increasing subsequence
        // j = last index of decreasing subsequence
        //
        // n is used as a virtual index meaning "empty".

        int[][] dp = new int[n + 1][n + 1];

        // -1 means this state is not reachable.
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -1;
            }
        }

        // Initially both subsequences are empty.
        dp[n][n] = 0;

        // Process every array element.
        for (int k = 0; k < n; k++) {

            int[][] next = new int[n + 1][n + 1];

            // Initialize next states.
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= n; j++) {
                    next[i][j] = -1;
                }
            }

            // Try every existing state.
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= n; j++) {

                    // State is not reachable.
                    if (dp[i][j] == -1) {
                        continue;
                    }

                    int selected = dp[i][j];

                    // ------------------------------------------------
                    // Option 1: Don't use arr[k]
                    // ------------------------------------------------
                    next[i][j] = Math.max(
                        next[i][j],
                        selected
                    );

                    // ------------------------------------------------
                    // Option 2: Add arr[k] to increasing subsequence
                    // ------------------------------------------------
                    if (i == n || arr[k] > arr[i]) {

                        next[k][j] = Math.max(
                            next[k][j],
                            selected + 1
                        );
                    }

                    // ------------------------------------------------
                    // Option 3: Add arr[k] to decreasing subsequence
                    // ------------------------------------------------
                    if (j == n || arr[k] < arr[j]) {

                        next[i][k] = Math.max(
                            next[i][k],
                            selected + 1
                        );
                    }
                }
            }

            // Move to the next element.
            dp = next;
        }

        // Find the maximum number of selected elements.
        int maxSelected = 0;

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                maxSelected = Math.max(
                    maxSelected,
                    dp[i][j]
                );
            }
        }

        // Minimum elements that cannot be selected.
        return n - maxSelected;
    }
}

12. Dry Run with a Small Example

Consider:

Code
arr = [1, 4, 2, 3]

We can choose:

Code
Increasing = [1, 2, 3]

Decreasing = [4]

All 4 elements are used.

Therefore:

Code
answer = 4 - 4 = 0

Initially

Code
dp[n][n] = 0

Both subsequences are empty.

Process 1

1 can be placed into the increasing subsequence:

Code
Increasing = [1]

or the decreasing subsequence:

Code
Decreasing = [1]

or skipped.

Process 4

If increasing ends with 1:

Code
1 < 4

so:

Code
Increasing = [1, 4]

is possible.

Alternatively, 4 can start the decreasing subsequence.

Process 2

If increasing currently ends at 1:

Code
1 < 2

so:

Code
Increasing = [1, 2]

is possible.

If decreasing ends at 4:

Code
2 < 4

so:

Code
Decreasing = [4, 2]

is also possible.

Process 3

We can eventually obtain:

Code
Increasing = [1, 2, 3]
Decreasing = [4]

All elements are selected.

Thus:

Code
maxSelected = 4
answer = 4 - 4 = 0

13. Why Strict Comparison Is Important

The problem specifically says strictly increasing and strictly decreasing.

Therefore:

Increasing

Java
arr[k] > arr[i]

not:

Java
arr[k] >= arr[i]

Decreasing

Java
arr[k] < arr[j]

not:

Java
arr[k] <= arr[j]

For example:

Code
[1, 2, 2, 3]

We cannot have:

Code
[1, 2, 2, 3]

as an increasing subsequence because the two 2s are equal.

14. Why Every Element Is Used at Most Once

At each iteration, the current element arr[k] is placed into one of:

Code
Increasing

or:

Code
Decreasing

or:

Code
Unused

When we put it into the increasing subsequence:

Java
next[k][j]

When we put it into the decreasing subsequence:

Java
next[i][k]

We never transition from the same state by adding arr[k] to both subsequences simultaneously.

Therefore, an element cannot be counted twice.

15. Why Do We Maximize Selected Elements?

The question asks:

What is the minimum number of elements that cannot be included?

Instead of directly minimizing unused elements, we maximize used elements.

If:

Code
n = total elements

and:

Code
maxSelected = maximum elements included

then:

Code
minimum unused = n - maxSelected

This transformation makes the DP much easier.

16. Complexity Analysis

There are:

Code
(n + 1) × (n + 1)

DP states.

For every array element, we visit all states.

Therefore:

Code
Time Complexity = O(n³)

because:

Code
n elements
× n possible i values
× n possible j values
= O(n³)

The DP table contains:

Code
(n + 1) × (n + 1)

elements.

So:

Code
Space Complexity = O(n²)

Although the problem's expected auxiliary space is listed as O(n³), this implementation actually uses only O(n²) auxiliary space because we maintain only the current and next DP tables.

17. Key Takeaway

The most important idea to remember is:

Track the last element of both subsequences.

For every new element:

Code
                 Current element
                       |
          +------------+------------+
          |            |            |
       Increase      Decrease      Skip
          |            |            |
    arr[k] > arr[i]  arr[k] < arr[j]

The DP state:

Java
dp[i][j]

captures everything we need to know about the two subsequences.

Finally:

Java
return n - maxSelected;

gives the minimum number of elements that cannot belong to either subsequence.