如何用动态规划解决指定规则下的数组最大累加和问题？

Great question! The brute-force permutation approach works for small lists, but it's way too slow for longer ones (since it runs in O(n!) time). Dynamic programming (DP) is the way to go here—let's break down how to model this problem efficiently.

Problem Recap #

Given a list of numbers (e.g., [4,5,2,3]), we remove elements one by one. The contribution to the sum depends on the element's neighbors when removed:

• If the element has two neighbors: contribution is current * max(left, right) + min(left, right)
• If the element has one neighbor: contribution is current * neighbor
• If it's the last element: add the element itself to the sum
  We need to find the optimal removal order to maximize the total accumulated sum.

Key Insight: Reverse the Removal Order #

Instead of thinking about which element to remove first, we'll reverse the problem: which element is removed last? This is a common DP trick for sequential removal problems (like the "burst balloons" problem). When an element is the last one removed from a subarray, its neighbors are fixed as the elements just outside that subarray (which haven't been removed yet). This lets us build solutions from smaller subarrays up to the full array.

DP State Definition #

Let dp[i][j] represent the maximum accumulated sum we can get by removing all elements in the subarray nums[i...j] (inclusive). When calculating dp[i][j], we assume the elements immediately before i (nums[i-1]) and after j (nums[j+1]) are still present—these act as the "boundaries" for the subarray.

Contribution Calculation #

For any element nums[k] (where i ≤ k ≤ j) chosen as the last element to remove from nums[i...j], we calculate its contribution based on the boundary elements:

• If neither boundary exists (i.e., we're dealing with the entire array): contribution is nums[k] (it's the last element left)
• Only the left boundary exists: contribution is nums[k] * left
• Only the right boundary exists: contribution is nums[k] * right
• Both boundaries exist: contribution is nums[k] * max(left, right) + min(left, right) (matches the problem's two-neighbor rule)

State Transition Equation #

To compute dp[i][j], we iterate over every possible k (from i to j) as the last element to remove. The maximum sum will be the highest value of:

dp[i][k-1] + dp[k+1][j] + contribution_of_k

Where:

• dp[i][k-1] = max sum from removing all elements in nums[i...k-1]
• dp[k+1][j] = max sum from removing all elements in nums[k+1...j]
• contribution_of_k = the value calculated above for removing nums[k] last

Boundary Conditions #

• If i > j: dp[i][j] = 0 (empty subarray, no contribution)
• If i == j: dp[i][j] is just the contribution of removing nums[i] with its current boundaries (since it's the only element in the subarray)

Python Implementation #

def max_accumulated_sum(nums):
    n = len(nums)
    # Initialize DP table: dp[i][j] stores max sum for subarray nums[i..j]
    dp = [[0] * n for _ in range(n)]
    
    def get_contribution(k, left_idx, right_idx):
        left = nums[left_idx] if left_idx >= 0 else None
        right = nums[right_idx] if right_idx < n else None
        
        if left is None and right is None:
            return nums[k]
        elif left is None:
            return nums[k] * right
        elif right is None:
            return nums[k] * left
        else:
            return nums[k] * max(left, right) + min(left, right)
    
    # Fill DP table by subarray length, starting from 1-element subarrays
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if i == j:
                # Single element case
                dp[i][j] = get_contribution(i, i-1, j+1)
            else:
                max_sum = -float('inf')
                # Try every possible k as the last element to remove
                for k in range(i, j + 1):
                    current_sum = dp[i][k-1] + dp[k+1][j] + get_contribution(k, i-1, j+1)
                    if current_sum > max_sum:
                        max_sum = current_sum
                dp[i][j] = max_sum
    
    return dp[0][n-1]

# Test with the example input
nums = [4,5,2,3]
print(max_accumulated_sum(nums))  # Output: 53

Time and Space Complexity #

• Time Complexity: O(n³) — we have O(n²) subarrays, and for each subarray we iterate up to O(n) elements as possible last elements to remove. This is exponentially better than the brute-force O(n!) approach.
• Space Complexity: O(n²) for storing the DP table.

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