D. Maximum Sum of Products
brute force; dp; implementation; 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.
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\)).
Print single integer — maximum possible sum after reversing at most one subarray (continuous subsegment) of \(a\).
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\).