Hackerrank《Sherlock and Cost》动态规划问题技术问询

Got it, let's break down how to solve this classic DP problem step by step—no fancy tricks, just clear state tracking to maximize that sum of absolute differences.

First, let's restate the problem to make sure we're on the same page:

Given an array B, construct an array A where every element A[i] can only be 1 or B[i]. Our goal is to maximize the total sum of |A[i] - A[i-1]| for all i from 1 to N.

The Dynamic Programming Approach #

The key insight here is that for each position in the array, we only need to track two possible states to compute the maximum sum up to that point:

• The maximum sum we can get if the current element A[i] is set to 1
• The maximum sum we can get if the current element A[i] is set to B[i]

We don't need to store an entire 2D array for this—we can just keep track of the previous position's two states, which cuts our space complexity down to O(1) (super efficient for large arrays!).

State Definitions & Transitions

Let's define two variables to hold the previous state values:

• prev_0: The maximum sum up to the (i-1)-th element when A[i-1] was set to 1
• prev_1: The maximum sum up to the (i-1)-th element when A[i-1] was set to B[i-1]

For each element starting from the second one (index 1), we calculate the current state values:

1. If we set A[i] to 1:
   We can come from either:

   • The previous element being 1 (adding 0 to the sum, since |1-1|=0)
   • The previous element being B[i-1] (adding |1 - B[i-1]| = B[i-1] - 1, since B values are positive integers ≥1)
     So: curr_0 = max(prev_0, prev_1 + (B[i-1] - 1))

2. If we set A[i] to B[i]:
   We can come from either:

   • The previous element being 1 (adding |B[i] - 1| = B[i] - 1 to the sum)
   • The previous element being B[i-1] (adding |B[i] - B[i-1]| to the sum)
     So: curr_1 = max(prev_0 + (B[i] - 1), prev_1 + abs(B[i] - B[i-1]))

Initial State

For the first element in the array, there's no previous element to calculate a difference with. So both starting states are 0:
prev_0 = 0, prev_1 = 0

Working Code Example (Python) #

Here's a clean implementation that uses the above logic—runs in O(n) time and uses constant space:

def cost(B):
    prev_0 = 0  # Tracks max sum when previous A element is 1
    prev_1 = 0  # Tracks max sum when previous A element is B[i-1]
    
    for i in range(1, len(B)):
        # Calculate current state values
        curr_0 = max(prev_0, prev_1 + (B[i-1] - 1))
        curr_1 = max(prev_0 + (B[i] - 1), prev_1 + abs(B[i] - B[i-1]))
        
        # Update previous states for next iteration
        prev_0, prev_1 = curr_0, curr_1
    
    # The answer is the maximum of the two final states
    return max(prev_0, prev_1)

# Test it out!
# Example 1: B = [4,7,1] → Optimal sum is 12 (A = [1,7,1])
# print(cost([4,7,1]))  # Output: 12
# Example 2: B = [1,2,3] → Optimal sum is 2
# print(cost([1,2,3]))  # Output: 2

Why This Works #

By focusing only on the two possible choices for each element and building up the maximum sum incrementally, we avoid having to brute-force all possible combinations of A (which would be impossible for large N). The state transitions ensure we always pick the choice that gives us the highest possible sum up to that point.

内容的提问来源于stack exchange，提问作者RichArt