📍 When Checkpoints Break LIS — A Deep Dive into Constrained Subsequences (DP Approach)

🔥 The Problem That Looks Like LIS… But Isn’t

You’re given an array.

You’re asked to find a non-decreasing subsequence.

Easy, right? Classic LIS problem.

But then comes the twist:

“You MUST pass through certain checkpoints.”

Now everything changes.

This is no longer a standard LIS problem.
This is a constraint-heavy optimization problem.

🧠 Real Problem Statement

You are given an array a[1..N] of positive integers and a set of p checkpoint indices cp1..P.

You need to find a subsequence such that:

It passes through all P checkpoints (each cp[k] must be included)
It is non-decreasing (i.e., a[i] ≤ a[j] for valid sequence order)
The total sum is maximized
📥 Input Format
First line: integer n (size of array)
Second line: integer p (number of checkpoints)
Next n lines: values of array a[i]
Next p lines: checkpoint indices cp[i]
📊 Constraints

1 ≤ n ≤ 500
1 ≤ p ≤ 10
1 ≤ a[i] ≤ 10^4
1 ≤ cp[i] ≤ n

🧪 Sample Test Cases
Case 1

Input:
5
2
10
20
15
30
40
2
4

Output:
100

👉 Valid subsequence:

10 → 20 → 30 → 40
Case 2
Input:

4
2
50
40
30
20
1
4

Output:
-1

👉 Why?

50 → 20 ❌ decreasing → invalid

⚠️ Why This Problem is Tricky

At first glance:

“Just run LIS.”

But here’s the catch:

• You cannot skip checkpoints
• You must maintain global non-decreasing order
• You must maximize sum, not length

💣 The First Critical Check

Before doing anything, validate checkpoints:

if (a[cp[i]] < a[cp[i-1]])
    return -1;

❌ Why?

If checkpoints themselves are decreasing:

a[cp[i-1]] > a[cp[i]]

Then no valid subsequence exists.

🧠 Key Insight (Game Changer)

Break the problem into segments.

📍 Think Like This:

Start → cp[0] → cp[1] → cp[2] → ... → cp[p-1] → End

Instead of solving globally:

👉 Solve each segment independently

⚙️ DP Strategy (Core Logic)

For each segment, we use:

dp[i] = maximum sum of non-decreasing subsequence ending at i

🔗 Transition

if (a[j] <= a[i])
    dp[i] = max(dp[i], dp[j] + a[i]);

🔒 Constraint Enforcement

We must ensure continuity across segments:

a[i] >= prev_val

Where:

prev_val = value of last checkpoint used

🔄 Full Flow

• Validate checkpoint order
• Process each segment using DP
• Ensure non-decreasing continuity
• Accumulate result
• Process remaining tail

💻 Final Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, p;
    cin >> n >> p;

    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> cp(p);
    for (int i = 0; i < p; i++) cin >> cp[i];

    // Check if checkpoints themselves are valid
    for (int i = 1; i < p; i++) {
        if (a[cp[i]] < a[cp[i-1]]) {
            cout << -1 << endl;
            return 0;
        }
    }

    int prev_idx = 1;
    int prev_val = 0;
    int total = 0;

    for (int k = 0; k < p; k++) {
        int L = prev_idx;
        int R = cp[k];

        // DP for this segment
        vector<int> dp(n+1, 0);

        for (int i = L; i <= R; i++) {
            if (a[i] < prev_val) continue;

            dp[i] = a[i];

            for (int j = L; j < i; j++) {
                if (a[j] <= a[i] && dp[j] > 0) {
                    dp[i] = max(dp[i], dp[j] + a[i]);
                }
            }
        }

        if (dp[R] == 0) {
            cout << -1 << endl;
            return 0;
        }

        total += dp[R];
        prev_val = a[R];
        prev_idx = R + 1;
    }

    // Handle remaining part after last checkpoint
    vector<int> dp(n+1, 0);

    for (int i = prev_idx; i <= n; i++) {
        if (a[i] < prev_val) continue;

        dp[i] = a[i];

        for (int j = prev_idx; j < i; j++) {
            if (a[j] <= a[i] && dp[j] > 0) {
                dp[i] = max(dp[i], dp[j] + a[i]);
            }
        }
    }

    int best = 0;
    for (int i = prev_idx; i <= n; i++) {
        best = max(best, dp[i]);
    }

    total += best;

    cout << total << endl;
    return 0;
}

⚡ Complexity
Time: O(N²)
Space: O(N)

Efficient enough for:

N ≤ 500

🧠 Key Takeaways

1. Constraints Change Everything

This is NOT LIS anymore — it's constrained LIS.

1. Break Big Problems

Global → Local segments → Combine

1. Always Validate Early

Fail fast:

if invalid → return -1

1. Max Sum ≠ Max Length

We optimize value, not size.

🎯 Interview One-Liner

“We split the array by checkpoints and run constrained LIS with maximum sum using DP.”

🚀 Final Thought

The hardest problems aren’t about writing code.

They’re about:

Understanding constraints
Breaking problems smartly
Handling edge cases