Increase Subarray Sums (Codeforces 1644C)
Tags: Greedy, dp

You are given an array $$$a_1, a_2, \dots, a_n$$$, consisting of $$$n$$$ integers. You are also given an integer value $$$x$$$.Let $$$f(k)$$$ be the maximum sum of a contiguous subarray of $$$a$$$ after applying the following operation: add $$$x$$$ to the elements on exactly $$$k$$$ distinct positions. An empty subarray should also be considered, it has sum $$$0$$$.Note that the subarray doesn't have to include all of the increased elements.Calculate the maximum value of $$$f(k)$$$ for all $$$k$$$ from $$$0$$$ to $$$n$$$ independently.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of testcases.The first line of the testcase contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 5000$$$; $$$0 \le x \le 10^5$$$) — the number of elements in the array and the value to add.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^5 \le a_i \le 10^5$$$).The sum of $$$n$$$ over all testcases doesn't exceed $$$5000$$$.

Output: For each testcase, print $$$n + 1$$$ integers — the maximum value of $$$f(k)$$$ for all $$$k$$$ from $$$0$$$ to $$$n$$$ independently.

Note: In the first testcase, it doesn't matter which elements you add $$$x$$$ to. The subarray with the maximum sum will always be the entire array. If you increase $$$k$$$ elements by $$$x$$$, $$$k \cdot x$$$ will be added to the sum.In the second testcase:   For $$$k = 0$$$, the empty subarray is the best option.  For $$$k = 1$$$, it's optimal to increase the element at position $$$3$$$. The best sum becomes $$$-1 + 5 = 4$$$ for a subarray $$$[3, 3]$$$.  For $$$k = 2$$$, it's optimal to increase the element at position $$$3$$$ and any other element. The best sum is still $$$4$$$ for a subarray $$$[3, 3]$$$.  For $$$k = 3$$$, you have to increase all elements. The best sum becomes $$$(-2 + 5) + (-7 + 5) + (-1 + 5) = 5$$$ for a subarray $$$[1, 3]$$$. 

Sample Inputs:
3
4 2
4 1 3 2
3 5
-2 -7 -1
10 2
-6 -1 -2 4 -6 -1 -4 4 -5 -4

Sample Outputs:
10 12 14 16 18
0 4 4 5
4 6 6 7 7 7 7 8 8 8 8

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
inf = pow(10, 9) + 1
for _ in range(t):
    (n, x) = map(int, input().split())
    a = list(map(int, input().split()))
    b = [0]
    for i in a:
        b.append(i + b[-1])
    ma = [0]
    for i in range(1, n + 1):
        mai = -inf
        for j in range(n - i + 1):
            mai = max(mai, b[i + j] - b[j])
        ma.append(mai)
    ans0 = [max(ma)]
    ma0 = ma[0]
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            ma[j] += x
            ma0 = max(ma0, ma[j])
        ans0.append(ma0)
    ans.append(' '.join(map(str, ans0)))
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    (n, x) = map(int, input().split())
    a = list(map(int, input().split()))
    pref = [0]
    for i in range(n):
        pref.append(pref[-1] + a[i])
    mxsum = [0]
    for i in range(1, n + 1):
        mxsum.append(float('-inf'))
        for j in range(n - i + 1):
            mxsum[i] = max(mxsum[i], pref[j + i] - pref[j])
    mxreached = mxsum[-1]
    for i in range(n - 1, -1, -1):
        mxreached = max(mxreached, mxsum[i])
        mxsum[i] = mxreached
    ans = []
    var = max(mxsum)
    for k in range(n + 1):
        ans.append(max(var, mxsum[k] + k * x))
        var = ans[-1]
    return ans
for _ in range(int(input())):
    print(*solve())

Solution (Python):
import io
import os
FILE_INPUT_MODE = 0
if FILE_INPUT_MODE >= 0:
    if FILE_INPUT_MODE == 1:
        CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
        FD = os.open(f'{CURRENT_DIR}\\input.txt', os.O_RDONLY)
    elif FILE_INPUT_MODE == 0:
        FD = 0
    DATA = io.BytesIO(os.read(FD, os.fstat(FD).st_size))
    if FD != 0:
        os.close(FD)

    def input():
        return DATA.readline().decode().rstrip('\r\n')

def solve():
    (n, x) = [int(word) for word in input().strip().split()]
    a = [int(word) for word in input().strip().split()]
    pre_sum = [0] * (n + 1)
    ans = [0] * (n + 1)
    for i in range(n):
        pre_sum[i] = pre_sum[i - 1] + a[i]
    for i in range(n):
        cur = -float('inf')
        for j in range(i + 1, -1, -1):
            cur = max(cur, pre_sum[i] - pre_sum[i - j])
            ans[j] = max(ans[j], cur + x * j)
    for i in range(1, n + 1):
        ans[i] = max(ans[i - 1], ans[i])
    return ' '.join(map(str, ans))

def main():
    t = int(input())
    for _ in range(t):
        print(solve())
if __name__ == '__main__':
    main()