Maximum Sum of Products (Codeforces 1519D)
Tags: Math, two pointers

You are given two integer arrays $$$a$$$ and $$$b$$$ of length $$$n$$$.You can reverse at most one subarray (continuous subsegment) of the array $$$a$$$. Your task is to reverse such a subarray that the sum $$$\sum\limits_{i=1}^n a_i \cdot b_i$$$ is maximized.

Input: The first line contains one integer $$$n$$$ ($$$1 \le n \le 5000$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^7$$$).The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^7$$$).

Output: Print single integer — maximum possible sum after reversing at most one subarray (continuous subsegment) of $$$a$$$.

Note: In the first example, you can reverse the subarray $$$[4, 5]$$$. Then $$$a = [2, 3, 2, 3, 1]$$$ and $$$2 \cdot 1 + 3 \cdot 3 + 2 \cdot 2 + 3 \cdot 4 + 1 \cdot 2 = 29$$$.In the second example, you don't need to use the reverse operation. $$$13 \cdot 2 + 37 \cdot 4 = 174$$$.In the third example, you can reverse the subarray $$$[3, 5]$$$. Then $$$a = [1, 8, 3, 6, 7, 6]$$$ and $$$1 \cdot 5 + 8 \cdot 9 + 3 \cdot 6 + 6 \cdot 8 + 7 \cdot 8 + 6 \cdot 6 = 235$$$.

Sample Inputs:
5
2 3 2 1 3
1 3 2 4 2

2
13 37
2 4

6
1 8 7 6 3 6
5 9 6 8 8 6

Sample Outputs:
29

174

235

Solution (Python):
rr = lambda : [*map(int, input().split())]
(n,) = rr()
a = rr()
b = rr()
m = p = sum((a[i] * b[i] for i in range(n)))
for i in range(n):

    def g(l, d=p, r=i + 1):
        global m
        while l >= 0 and r < n:
            d -= (a[l] - a[r]) * (b[l] - b[r])
            m = max(m, d)
            l -= 1
            r += 1
    g(i - 1)
    g(i)
print(m)

Solution (Python):
I = lambda : [*map(int, input().split())]
(n,) = I()
a = I()
b = I()
m = p = sum((a[i] * b[i] for i in range(n)))
for i in range(n):

    def g(l, d=p, r=i + 1):
        global m
        while l >= 0 and r < n:
            d -= (a[l] - a[r]) * (b[l] - b[r])
            m = max(m, d)
            l -= 1
            r += 1
    g(i - 1)
    g(i)
print(m)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
m = p = sum((a[i] * b[i] for i in range(n)))

def g(l, r, d=p):
    global m
    while l >= 0 and r < n:
        d -= (a[l] - a[r]) * (b[l] - b[r])
        m = max(m, d)
        l -= 1
        r += 1
for i in range(n):
    g(i - 1, i + 1)
    g(i, i + 1)
print(m)