Maximum Subarray (Codeforces 1796D)
Tags: Greedy, two pointers

You are given an array $$$a_1, a_2, \dots, a_n$$$, consisting of $$$n$$$ integers. You are also given two integers $$$k$$$ and $$$x$$$.You have to perform the following operation exactly once: add $$$x$$$ to the elements on exactly $$$k$$$ distinct positions, and subtract $$$x$$$ from all the others.For example, if $$$a = [2, -1, 2, 3]$$$, $$$k = 1$$$, $$$x = 2$$$, and we have picked the first element, then after the operation the array $$$a = [4, -3, 0, 1]$$$.Let $$$f(a)$$$ be the maximum possible sum of a subarray of $$$a$$$. The subarray of $$$a$$$ is a contiguous part of the array $$$a$$$, i. e. the array $$$a_i, a_{i + 1}, \dots, a_j$$$ for some $$$1 \le i \le j \le n$$$. An empty subarray should also be considered, it has sum $$$0$$$.Let the array $$$a'$$$ be the array $$$a$$$ after applying the aforementioned operation. Apply the operation in such a way that $$$f(a')$$$ is the maximum possible, and print the maximum possible value of $$$f(a')$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains three integers $$$n$$$, $$$k$$$ and $$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le \min(20, n)$$$; $$$-10^9 \le x \le 10^9$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$). The sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print one integer — the maximum possible value of $$$f(a')$$$.


Sample Inputs:
4
4 1 2
2 -1 2 3
2 2 3
-1 2
3 0 5
3 2 4
6 2 -8
4 -1 9 -3 7 -8

Sample Outputs:
5
7
0
44

Solution (Python):
import sys
ipt = sys.stdin.readline
for _ in range(int(ipt())):
    (N, K, X) = list(map(int, ipt().split()))
    A = list(map(int, ipt().split()))
    if X >= 0:
        S = [0]
        for a in A:
            S.append(S[-1] + a - X)
        ans = 0
        mi = 0
        for i in range(N):
            ma = 0
            t = 0
            for j in range(i, max(-1, i - K), -1):
                t += A[j] + X
                ma = max(ma, t)
            if i >= K:
                mi = min(mi, S[i + 1 - K])
                ma = max(ma, S[i + 1] - mi + 2 * X * K)
            ans = max(ans, ma)
        print(ans)
    else:
        S = [0]
        for a in A:
            S.append(S[-1] + a - X)
        ans = 0
        mi = min(S[:K + 1])
        for i in range(K, N - K):
            ans = max(ans, S[i + 1] - mi)
            mi = min(mi, S[i + 1])
        for i in range(K):
            for j in range(i + 1, N + 1):
                if j - i <= N - K:
                    ans = max(ans, S[j] - S[i])
                else:
                    ans = max(ans, S[j] - S[i] + (j - i - (N - K)) * X * 2)
        for i in range(N - K + 1, N + 1):
            for j in range(i):
                if i - j <= N - K:
                    ans = max(ans, S[i] - S[j])
                else:
                    ans = max(ans, S[i] - S[j] + (i - j - (N - K)) * X * 2)
        print(ans)

Solution (Python):
import math
T = int(input())
while T:
    (n, k, x) = map(int, input().split())
    A = list(map(int, input().split()))
    A = [-float('inf')] + A
    if x >= 0:
        pre = [-float('inf')] * (n + 1)
        ret = 0
        for i in range(1, n + 1):
            pre[i] = max(pre[i - 1] + A[i] - x, A[i] - x)
            ret = max(ret, pre[i])
        for i in range(1, n - k + 2):
            dp = [-float('inf')] * (k + 3)
            dp[0] = pre[i - 1]
            for j in range(1, k + 1):
                dp[j] = max(dp[j - 1] + A[i + j - 1] + x, A[i + j - 1] + x)
                ret = max(ret, dp[j])
        print(ret)
    else:
        ret = 0
        for l in range(k + 1):
            dp = [-float('inf')] * (n + 2)
            r = n - k + l + 1
            for j in range(1, n + 1):
                if j <= l or j >= r:
                    dp[j] = max(dp[j - 1] + A[j] + x, A[j] + x)
                else:
                    dp[j] = max(dp[j - 1] + A[j] - x, A[j] - x)
                ret = max(ret, dp[j])
        print(ret)
    T -= 1

Solution (Python):
import math
from bisect import bisect_right
from bisect import bisect_left
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from random import randrange

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
t = int(input())
for _ in range(t):
    (n, k, x) = map(int, input().split())
    b = [0] + list(map(int, input().split()))
    ans = 0
    pre = [0 for i in range(n + 1)]
    prem = [0 for i in range(n + 1)]
    for i in range(1, n + 1):
        pre[i] = pre[i - 1] + b[i]
    for i in range(1, n + 1):
        prem[i] = min(prem[i - 1], pre[i - 1] - (i - 1) * x)
    if x >= 0:
        mi = 0
        for i in range(1, n + 1):
            j = i
            while i - j + 1 <= k and j >= 1:
                ans = max(ans, pre[i] - pre[j - 1] + (i - j + 1) * x)
                j += -1
            if i >= k:
                ans = max(ans, pre[i] - prem[i - k] + (2 * k - i) * x)
    else:
        i = 1
        mi = 0
        while i <= n - k:
            ans = max(ans, pre[i] - mi - i * x)
            mi = min(mi, pre[i] - i * x)
            i += 1
        while i <= n:
            j = i
            while j >= 1:
                l = i - j + 1
                if n - l >= k:
                    ans = max(ans, pre[i] - pre[j - 1] - l * x)
                else:
                    ans = max(ans, pre[i] - pre[j - 1] - l * x + 2 * x * (k - (n - l)))
                j += -1
            i += 1
    print(ans)