How to Maximize Subarray Sum with One Element Replacement (DP Solution)

Problem Statement

Given an array of n integers, you may change at most one element to a given value x. For each query, output the maximum possible sum of a contiguous subarray after the optional modification.

Input

First line integer t (1 ≤ t ≤ 100000) – number of queries. For each query: first line contains n and x (1 ≤ n ≤ 200000, -10^9 ≤ x ≤ 10^9). Second line contains n integers a_i (-10^9 ≤ a_i ≤ 10^9). The sum of n over all queries does not exceed 200000.

Output

For each query output a single integer – the maximum subarray sum achievable.

Solution Idea

The problem reduces to the classic maximum subarray sum (Kadane/LeetCode 53) with an additional “one‑time replacement” operation, similar to stock‑buy‑sell DP.

Use dynamic programming with two states for each position i: dp[i][0]: maximum subarray sum ending at i without having used the replacement. dp[i][1]: maximum subarray sum ending at i after the replacement has been used.

Transition:

If dp[i-1][0] < 0, start a new subarray: dp[i][0] = nums[i]; otherwise extend: dp[i][0] = nums[i] + dp[i-1][0].

For the replaced state, either replace the current element ( dp[i-1][0] + x) or replace an earlier element ( dp[i-1][1] + nums[i]): dp[i][1] = max(dp[i-1][0] + x, dp[i-1][1] + nums[i]).

Maintain the global answer as the maximum of all dp[i][0] and dp[i][1].

Reference Implementation (Python)

# DP solution for the problem
def sol(nums, n, x):
    dp = [[0, 0] for _ in range(n)]
    dp[0] = [nums[0], x]
    ans = max(dp[0])
    for i in range(1, n):
        if dp[i-1][0] < 0:
            dp[i][0] = nums[i]
        else:
            dp[i][0] = nums[i] + dp[i-1][0]
        dp[i][1] = max(dp[i-1][0] + x, dp[i-1][1] + nums[i])
        ans = max(ans, dp[i][0], dp[i][1])
    return ans

t = int(input())
for _ in range(t):
    n, x = map(int, input().split())
    nums = list(map(int, input().split()))
    print(sol(nums, n, x))

Complexity Analysis

Time complexity O(n) per query, requiring a single pass over the array.

Space complexity O(n) for the DP table; it can be reduced to O(1) by keeping only the previous row.