Q2 – Alternating Sign Subsequence

📝 Problem Statement

You are given an array a of N integers (each element is non-zero) and a bonus value B.

You need to select a subsequence of the array such that consecutive chosen elements have strictly alternating signs — i.e., a positive element must be followed by a negative element and vice versa.

The score of the chosen subsequence is defined as:

Score = Sum of selected elements + B × (L − 1)    if L ≥ 2
Score = element value    if L = 1
Score = 0    if no element is selected (empty subsequence)

where L is the length of the selected subsequence.

Goal: Find the maximum possible score.

⚡ Function Signature

int solve(int N, int B, vector<int>& a)

Parameters

Parameter	Type	Description
`N`	`int`	Size of the array
`B`	`int`	Bonus value added per transition between opposite signs
`a`	`vector<int>&`	The array of N non-zero integers

Returns

An int — the maximum score achievable.

📏 Constraints

1 ≤ N ≤ 10⁵
-10⁹ ≤ a[i] ≤ 10⁹, a[i] ≠ 0
0 ≤ B ≤ 10⁹

Note: The answer may be large. Intermediate computations should use long long.

🧪 Examples

Example 1

Input

N = 5, B = 10
a = [1, -5, 2, -8, 3]

Output

Explanation: Select the entire array [1, -5, 2, -8, 3]. Signs alternate: +, -, +, -, +. L = 5.
Score = (1 − 5 + 2 − 8 + 3) + 10 × (5 − 1) = −7 + 40 = 33.

Example 2

Input

N = 4, B = 0
a = [10, -20, 5, -1]

Output

Explanation: With B = 0, there is no bonus for transitions. Picking just [10] gives score = 10, which is the best.

Example 3

Input

N = 5, B = 100
a = [10, 20, 30, 40, 50]

Output

Explanation: All elements are positive — no alternation is possible. The best single element is 50.

💡 Approach Hint

Use a linear scan maintaining two states:

best_pos — best score of a subsequence that ends with a positive element
best_neg — best score of a subsequence that ends with a negative element

For each element, either start a new subsequence (score = element) or extend from the opposite-sign best (score = opposite_best + element + B).

Time Complexity: O(N) | Space Complexity: O(1)

✅ Solution 1 — Copilot's Approach

Complete Code

int solve(int N, int B, vector<int>& a) {
    const long long NEG_INF = -1e18;
    long long best_pos = NEG_INF;
    long long best_neg = NEG_INF;

    for (int i = 0; i < N; i++) {
        if (a[i] > 0) {
            best_pos = max(best_pos,
                       max((long long)a[i],
                            best_neg + a[i] + B));
        } else {
            best_neg = max(best_neg,
                       max((long long)a[i],
                            best_pos + a[i] + B));
        }
    }

    long long ans = 0;
    if (best_pos > ans) ans = best_pos;
    if (best_neg > ans) ans = best_neg;
    return (int)ans;
}

Line-by-Line Explanation

Line	Explanation
`const long long NEG_INF = -1e18;`	A safely large negative sentinel value. We use `-1e18` instead of `LLONG_MIN` so that adding a value to it won't cause integer overflow. Any real subsequence score will be larger than this.
`long long best_pos = NEG_INF;`	Tracks the maximum score achievable by any subsequence seen so far that ends with a positive element. Initialized to NEG_INF meaning "no valid subsequence yet".
`long long best_neg = NEG_INF;`	Same idea — tracks the best score of any subsequence that ends with a negative element.
`for (int i = 0; i < N; i++)`	Linear scan through every element of the array exactly once → O(N).
`if (a[i] > 0)`	Current element is positive, so it can only appear at the end of a subsequence whose previous element (if any) was negative.
`max((long long)a[i], best_neg + a[i] + B)`	Two choices for this positive element: (a) `a[i]` — start a brand-new subsequence of length 1 (no bonus). (b) `best_neg + a[i] + B` — extend the best negative-ending subsequence by appending this element. We get +B because each new transition earns the bonus. We pick whichever is larger.
`best_pos = max(best_pos, ...)`	We keep the overall best across all positive-ending subsequences. If some earlier element gave a higher `best_pos`, we don't throw it away — the outer `max` retains it.
`else { ... best_neg ... }`	Mirror logic for negative elements: extend from `best_pos` or start fresh. Exactly symmetric to the positive branch.
`long long ans = 0;`	Start with 0 (the score of the empty subsequence — choosing nothing).
`if (best_pos > ans) ans = best_pos;`	If the best positive-ending subsequence beats the empty choice, use it.
`if (best_neg > ans) ans = best_neg;`	Same check for the best negative-ending subsequence. The overall answer is `max(0, best_pos, best_neg)`.
`return (int)ans;`	Cast back to `int` to match the function signature. (If values can be very large, the return type should ideally be `long long`.)

Why it works: Since only one branch (positive or negative) executes per element, updating best_pos never contaminates best_neg within the same iteration. No need to save previous values.

✅ Solution 2 — User's Approach

Complete Code

int solve(int N, int B, vector<int>& a) {
    long long pos = LLONG_MIN;  // ends with positive
    long long neg = LLONG_MIN;  // ends with negative

    for (int x : a) {
        long long prev_pos = pos;
        long long prev_neg = neg;

        if (x > 0) {
            long long new_pos = x;  // start new

            if (prev_neg != LLONG_MIN)
                new_pos = max(new_pos, prev_neg + x + B);

            pos = max(prev_pos, new_pos);
        } else {
            long long new_neg = x;

            if (prev_pos != LLONG_MIN)
                new_neg = max(new_neg, prev_pos + x + B);

            neg = max(prev_neg, new_neg);
        }
    }

    return max({0LL, pos, neg});
}

Line-by-Line Explanation

Line	Explanation
`long long pos = LLONG_MIN;`	Best score of any subsequence ending with a positive element. Initialized to `LLONG_MIN` (≈ −9.2 × 10¹⁸) meaning "no positive-ending subsequence exists yet".
`long long neg = LLONG_MIN;`	Same for subsequences ending with a negative element.
`for (int x : a)`	Range-based for loop — iterate through every element. Equivalent to indexing with `i`.
`long long prev_pos = pos;` `long long prev_neg = neg;`	Snapshot the current DP values before this iteration modifies them. This is a defensive measure — it guarantees we use the state from before processing element `x`. (Technically safe without it since only one branch executes, but it makes the logic bulletproof and easier to reason about.)
`if (x > 0)`	Element is positive → it can only sit at the end of a subsequence whose previous element was negative.
`long long new_pos = x;`	Option A: Start a fresh subsequence containing just `x`. Score = x, no bonus.
`if (prev_neg != LLONG_MIN)`	Guard check: Only try to extend if a valid negative-ending subsequence actually exists. Without this, `LLONG_MIN + x + B` would overflow (undefined behavior in C++). This is the key safety difference from Solution 1 which uses `-1e18` instead.
`new_pos = max(new_pos, prev_neg + x + B);`	Option B: Extend the best negative-ending subsequence by appending `x`. Gains the element's value plus one bonus `B` for the sign transition. Pick whichever option (A or B) gives a higher score.
`pos = max(prev_pos, new_pos);`	Keep the overall best positive-ending score. If an earlier iteration produced a higher `pos`, we don't discard it. This is the "carry forward the best" step.
`else { ... neg ... }`	Mirror logic for negative elements: try extending from `prev_pos` or start fresh. Same guard check prevents overflow. Entirely symmetric to the positive branch.
`return max({0LL, pos, neg});`	Take the best of three candidates: • `0` — the empty subsequence (pick nothing). • `pos` — best subsequence ending with a positive element. • `neg` — best subsequence ending with a negative element. Uses `initializer_list` overload of `max`. Even if `pos` or `neg` is still `LLONG_MIN`, it's a valid `long long` and `0` will win.

⚖️ Comparison of Both Solutions

Aspect	Solution 1 (Copilot)	Solution 2 (User)
Sentinel value	`-1e18` — safe to add to without overflow	`LLONG_MIN` — must guard with `!= LLONG_MIN` check
Overflow protection	Implicit — `-1e18 + x + B` never overflows	Explicit — `if` guard prevents `LLONG_MIN + x + B`
Prev-value snapshot	Not needed (only one branch runs per element)	Taken defensively — clearer intent, same result
Final answer	Manual `if` checks against `ans = 0`	`max({0LL, pos, neg})` — concise one-liner
Complexity	O(N) time, O(1) space	O(N) time, O(1) space
Correctness	✅ Passes all examples	✅ Passes all examples

Verdict: Both solutions are correct and equally efficient. They differ only in style — Solution 1 avoids the guard check by using a "safe" sentinel; Solution 2 uses LLONG_MIN with explicit guards, which is arguably more precise and defensive.

Q2 — Alternating Sign Subsequence

📝 Problem Statement

⚡ Function Signature

Parameters

Returns

📏 Constraints

🧪 Examples

Example 1

Example 2

Example 3

💡 Approach Hint

✅ Solution 1 — Copilot's Approach

Complete Code

Line-by-Line Explanation

✅ Solution 2 — User's Approach

Complete Code

Line-by-Line Explanation

⚖️ Comparison of Both Solutions