Maximize Sum of Adjacent Differences with 1 Replacement

Problem Statement

Given an integer array arr[], we are allowed to replace any number of elements with 1.

Our goal is to find the maximum possible sum of absolute differences between consecutive elements after making any number of replacements.

For example:

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

The adjacent differences are:

|3 - 2| + |2 - 1| + |1 - 4| + |4 - 5|
= 1 + 1 + 3 + 1
= 6

But we can replace some elements with 1.

For example:

[3, 1, 1, 4, 1]

Now:

|3 - 1| + |1 - 1| + |1 - 4| + |4 - 1|
= 2 + 0 + 3 + 3
= 8

Therefore, the answer is:

Understanding the Problem

For every element, we have exactly two choices:

Choice 1: Keep the original value

For example:

arr[i] = 4

We can keep it as:

Choice 2: Replace it with 1

We can change:

4 → 1

So every element has two possible states:

Original value
       OR
      1

This naturally suggests Dynamic Programming.

Why Greedy Is Difficult

At first, it might seem that we should simply replace every element with 1.

But that is not always optimal.

Consider:

[1, 5]

If we don't modify anything:

|1 - 5| = 4

If we replace 5 with 1:

|1 - 1| = 0

So replacing an element can actually reduce the answer.

The decision for one element also affects the difference with both its neighbors.

Therefore, we need to consider both possibilities using Dynamic Programming.

DP States

We maintain two DP values.

`dp0`

dp0 represents:

Maximum sum obtained so far when the current element is kept unchanged.

For example, if the current element is:

arr[i] = 4

then the current value is 4.

`dp1`

dp1 represents:

Maximum sum obtained so far when the current element is replaced by 1.

So if:

arr[i] = 4

then the current value becomes:

Transition

Suppose we are currently processing:

arr[i]

There are two possibilities.

Case 1: Keep `arr[i]`

The current value is:

arr[i]

The previous element could have been:

Previous element was unchanged

Previous value:

arr[i - 1]

Difference:

|arr[i] - arr[i - 1]|

Total:

dp0 + |arr[i] - arr[i - 1]|

Previous element was replaced

Previous value:

Difference:

|arr[i] - 1|

Total:

dp1 + |arr[i] - 1|

Therefore:

newDp0 = max(
    dp0 + |arr[i] - arr[i - 1]|,
    dp1 + |arr[i] - 1|
)

Case 2: Replace `arr[i]` with `1`

Now the current value is:

Again, there are two possibilities for the previous element.

Previous element was unchanged

Previous value:

arr[i - 1]

Difference:

|1 - arr[i - 1]|

Total:

dp0 + |1 - arr[i - 1]|

Previous element was also replaced

Both values are 1.

Therefore:

|1 - 1| = 0

Total:

dp1 + 0

So:

newDp1 = max(
    dp0 + |1 - arr[i - 1]|,
    dp1
)

Java Implementation

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

        if (n <= 1) {
            return 0;
        }

        // Current element is NOT replaced
        long dp0 = 0;

        // Current element IS replaced with 1
        long dp1 = 0;

        for (int i = 1; i < n; i++) {

            long newDp0 = Math.max(
                dp0 + Math.abs(arr[i] - arr[i - 1]),
                dp1 + Math.abs(arr[i] - 1)
            );

            long newDp1 = Math.max(
                dp0 + Math.abs(1 - arr[i - 1]),
                dp1
            );

            dp0 = newDp0;
            dp1 = newDp1;
        }

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

Code Explanation

Let's understand the code line by line.

Step 1: Array Size

int n = arr.length;

This stores the number of elements in the array.

Step 2: Handle One Element

if (n <= 1) {
    return 0;
}

If there is only one element, there are no consecutive pairs.

For example:

[5]

There is no adjacent difference.

Therefore:

answer = 0

Step 3: Initialize DP

long dp0 = 0;
long dp1 = 0;

Initially, there is no adjacent pair.

So both states start from 0.

dp0 = current element kept
dp1 = current element changed to 1

We use long internally so that the calculation is safe for larger sums.

Step 4: Traverse the Array

for (int i = 1; i < n; i++) {

We start from index 1 because we need a previous element to calculate:

|arr[i] - arr[i - 1]|

Step 5: Calculate `newDp0`

long newDp0 = Math.max(
    dp0 + Math.abs(arr[i] - arr[i - 1]),
    dp1 + Math.abs(arr[i] - 1)
);

This calculates the best answer when the current element is not replaced.

There are two possibilities.

Previous was unchanged

dp0 + Math.abs(arr[i] - arr[i - 1])

Previous was replaced

dp1 + Math.abs(arr[i] - 1)

We take whichever is larger:

Math.max(...)

Step 6: Calculate `newDp1`

long newDp1 = Math.max(
    dp0 + Math.abs(1 - arr[i - 1]),
    dp1
);

This calculates the best answer when the current element is replaced with 1.

Again, two possibilities.

Previous was unchanged

dp0 + Math.abs(1 - arr[i - 1])

Previous was replaced

The previous value is 1 and current value is also 1.

Therefore:

|1 - 1| = 0

So we simply have:

dp1

Step 7: Move to the Next Position

dp0 = newDp0;
dp1 = newDp1;

The newly calculated states become the previous states for the next iteration.

This is what allows us to solve the problem using only two variables instead of a complete DP array.

Step 8: Return the Maximum

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

At the end, the final element can either be:

original value

or:

Therefore, we take the maximum of:

dp0
dp1

Dry Run

Consider:

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

Initially:

dp0 = 0
dp1 = 0

i = 1

Current:

arr[1] = 2

Keep 2:

newDp0 = max(
    0 + |2 - 3|,
    0 + |2 - 1|
)

= max(1, 1)
= 1

Replace 2 with 1:

newDp1 = max(
    0 + |1 - 3|,
    0
)

= max(2, 0)
= 2

Now:

dp0 = 1
dp1 = 2

i = 2

Current:

arr[2] = 1

Keep 1:

newDp0 = max(
    1 + |1 - 2|,
    2 + |1 - 1|
)

= max(2, 2)
= 2

Replace with 1:

newDp1 = max(
    1 + |1 - 2|,
    2
)

= max(2, 2)
= 2

Now:

dp0 = 2
dp1 = 2

i = 3

Current:

arr[3] = 4

Keep 4:

newDp0 = max(
    2 + |4 - 1|,
    2 + |4 - 1|
)

= max(5, 5)
= 5

Replace with 1:

newDp1 = max(
    2 + |1 - 1|,
    2
)

= 2

Now:

dp0 = 5
dp1 = 2

i = 4

Current:

arr[4] = 5

Keep 5:

newDp0 = max(
    5 + |5 - 4|,
    2 + |5 - 1|
)

= max(6, 6)
= 6

Replace with 1:

newDp1 = max(
    5 + |1 - 4|,
    2
)

= max(8, 2)
= 8

Finally:

dp0 = 6
dp1 = 8

Therefore:

answer = max(6, 8)
       = 8

Why the Answer Becomes 8

The DP effectively discovers the optimal modified array:

[3, 1, 1, 4, 1]

The sum is:

|3 - 1| = 2
|1 - 1| = 0
|1 - 4| = 3
|4 - 1| = 3

Total:

2 + 0 + 3 + 3 = 8

Example 2

Consider:

arr = [1, 5]

Without modification:

|1 - 5| = 4

The DP will compare:

Keep 5:
|1 - 5| = 4

and:

Replace 5:
|1 - 1| = 0

Therefore:

answer = 4

Complexity

There are n elements and we process each element exactly once.

Time Complexity

O(n)

For:

n = 100000

this is efficient.

Space Complexity

Although a traditional DP solution could use an array and require:

O(n)

space, this implementation only stores the previous two states:

dp0
dp1

Therefore, the actual auxiliary space is:

O(1)

Key Takeaway

The important idea is to recognize that each element has only two possible states:

State 0 → Keep arr[i]
State 1 → Replace arr[i] with 1

For every position, we calculate the best result for both states.

The complete DP is:

newDp0 = max(
    dp0 + |arr[i] - arr[i-1]|,
    dp1 + |arr[i] - 1|
)

newDp1 = max(
    dp0 + |1 - arr[i-1]|,
    dp1
)

This reduces the problem to a simple two-state Dynamic Programming solution.

Final Code

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

        if (n <= 1) {
            return 0;
        }

        long dp0 = 0;
        long dp1 = 0;

        for (int i = 1; i < n; i++) {

            long newDp0 = Math.max(
                dp0 + Math.abs(arr[i] - arr[i - 1]),
                dp1 + Math.abs(arr[i] - 1)
            );

            long newDp1 = Math.max(
                dp0 + Math.abs(1 - arr[i - 1]),
                dp1
            );

            dp0 = newDp0;
            dp1 = newDp1;
        }

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

Interview Tip: When you see a problem where every element has a small number of choices and the current choice depends only on the previous element, think about DP with states. Here, the two states are simply "keep" and "replace with 1".

Summary

The important idea is to recognize that each element has only two possible states: State 0 → Keep arr[i] and State 1 → Replace arr[i] with 1. For every position, we calculate the best result for both states. This reduces the problem to a simple two-state Dynamic Programming solution.

Problem Statement

Understanding the Problem

Choice 1: Keep the original value

Choice 2: Replace it with 1

Why Greedy Is Difficult

DP States

dp0

dp1

Transition

Case 1: Keep arr[i]

Previous element was unchanged

Previous element was replaced

Case 2: Replace arr[i] with 1

Previous element was unchanged

Previous element was also replaced

Java Implementation

Code Explanation

Step 1: Array Size

Step 2: Handle One Element

Step 3: Initialize DP

Step 4: Traverse the Array

Step 5: Calculate newDp0

Previous was unchanged

Previous was replaced

Step 6: Calculate newDp1

Previous was unchanged

Previous was replaced

Step 7: Move to the Next Position

Step 8: Return the Maximum

Dry Run

i = 1

i = 2

i = 3

i = 4

Why the Answer Becomes 8

Example 2

Complexity

Time Complexity

Space Complexity

Key Takeaway

Final Code

Summary

`dp0`

`dp1`

Case 1: Keep `arr[i]`

Case 2: Replace `arr[i]` with `1`

Step 5: Calculate `newDp0`

Step 6: Calculate `newDp1`