Max Adjacent Diffs Sum with 1 Replacements

Problem Overview

Any entry may stay as written or become 1.

Intuition

Any entry may stay as written or become 1. The score is the sum of absolute gaps between neighbors. At each index only two ending values matter: the original number or 1. Remember the best score for each ending choice and extend both options from the previous index.

Algorithm

1If length is at most 1, return 0.
2Let dp0 be the best sum ending with arr[i] kept, and dp1 the best ending with 1.
3For each i from 1 to n-1, compute new dp0 from both previous states using |arr[i] - prev|.
4Compute new dp1 from previous kept using |1 - arr[i-1]|, and from previous 1 using 0.
5Return the max of the final dp0 and dp1.

Example Walkthrough

Input: arr = [3, 2, 1, 4, 5]

1. Replace some values with 1 to stretch large neighbors, for example [3, 1, 1, 4, 1].
2. Gaps become 2 + 0 + 3 + 3 = 8.
3. Rolling DP reaches the same maximum without enumerating every mask.

Output: 8

Common Pitfalls

• You may change any number of positions to 1, not only one position.
• Keep only the previous two scores. A full n by 2 table wastes space.
• When both ends are 1 the gap is 0, so the replace state carries dp1 forward unchanged.
• n = 1 has no adjacent pair, so answer 0.

Max Adjacent Diffs Sum with 1 Replacements.java

Java

// Approach: Each index may stay as arr[i] or become 1. Keep two rolling scores:
// best sum ending with the original value, and best ending with 1. At each step
// take the better of the two previous states plus the adjacent absolute gap.
// Complexity: O(n) time and O(1) extra space.
class Solution {

    public int maxDiffSum(int[] arr) {
        int n = arr.length;
        if (n == 1) {
            return 0;
        }

        // dp0 = best sum up to index i when arr[i] is kept
        // dp1 = best sum up to index i when arr[i] is replaced by 1
        int dp0 = 0, dp1 = 0;

        for (int i = 1; i < n; i++) {
            int ndp0 = Math.max(dp0 + Math.abs(arr[i] - arr[i - 1]),
                    dp1 + Math.abs(arr[i] - 1));
            int ndp1 = Math.max(dp0 + Math.abs(1 - arr[i - 1]),
                    dp1); // |1 - 1| = 0
            dp0 = ndp0;
            dp1 = ndp1;
        }

        return Math.max(dp0, dp1);
    }
}

Was this solution helpful?