Swap and Take (Codeforces 1736E)
Tags: Greedy, dp

You're given an array consisting of $$$n$$$ integers. You have to perform $$$n$$$ turns.Initially your score is $$$0$$$.On the $$$i$$$-th turn, you are allowed to leave the array as it is or swap any one pair of $$$2$$$ adjacent elements in the array and change exactly one of them to $$$0$$$(and leave the value of other element unchanged) after swapping. In either case(whether you swap or not), after this you add $$$a_i$$$ to your score. What's the maximum possible score you can get?

Input: The first line contains a single integer $$$n$$$ ($$$2 \le n \le 500$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

Output: Print a single integer — the maximum possible score.

Note: In the first example, to get the maximum score we do as follows. Do nothing on the first turn, add $$$3$$$ to the score. Swap the first and the second elements and turn $$$1$$$ to $$$0$$$ on the second turn, and add $$$3$$$ to the score. The final score is $$$6$$$.

Sample Inputs:
2
3 1

5
7 3 9 6 12

Sample Outputs:
6

52

Solution (Python):
(n, a) = (int(input()), list(map(int, input().split())))
INF = 10 ** 9 + 7
f = [[-INF] * (n + 1) for j in range(n + 1)]
s = [[0] * (n + 1) for j in range(n + 1)]
ans = -INF
for i in range(1, n + 1):
    for j in range(n, 0, -1):
        for k in range(i, -1, -1):
            if k:
                f[j][k] = f[j][k - 1] + a[j - 1]
            if j >= i and i + k >= j:
                f[j][k] = max(f[j][k], s[j - 1][i + k - j] + a[j - 1])
            ans = max(ans, f[j][k])
    for j in range(1, n + 1):
        for k in range(i + 1):
            s[j][k] = max(s[j - 1][k], f[j][k])
print(ans)

Solution (Python):
(n, a) = (int(input()), list(map(int, input().split())))
INF = 10 ** 9 + 7
f = [[-INF] * (n + 1) for j in range(n + 1)]
s = [[0] * (n + 1) for j in range(n + 1)]
ans = -INF
for i in range(1, n + 1):
    for j in range(n, 0, -1):
        for k in range(i, -1, -1):
            if k:
                f[j][k] = f[j][k - 1] + a[j - 1]
            if j >= i and i + k >= j:
                f[j][k] = max(f[j][k], s[j - 1][i + k - j] + a[j - 1])
            ans = max(ans, f[j][k])
    for j in range(1, n + 1):
        for k in range(i + 1):
            s[j][k] = max(s[j - 1][k], f[j][k])
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 9 + 7
f = [[-INF] * (n + 1) for _ in range(n + 1)]
s = [[0] * (n + 1) for _ in range(n + 1)]
ans = -INF
for i in range(1, n + 1):
    for j in range(n, 0, -1):
        for k in range(i, -1, -1):
            if k:
                f[j][k] = f[j][k - 1] + a[j - 1]
            if j >= i and i + k >= j:
                f[j][k] = max(f[j][k], s[j - 1][i + k - j] + a[j - 1])
            ans = max(ans, f[j][k])
    for j in range(1, n + 1):
        for k in range(i + 1):
            s[j][k] = max(s[j - 1][k], f[j][k])
print(ans)