Problem statement

https://binarysearch.com/problems/Outstanding-Move/

Solution

This is an easy version of BinarySarch 0389 Outstanding Move problem, where we can have O(n^2) algorithm.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, A):
        base = sum(i * x for i, x in enumerate(A, 1))
        P = [0] + list(accumulate(A))
        ans, n = 0, len(A)
        for i in range(n):
            for j in range(n + 1):
                ans = max(ans, P[i] - P[j] - (i - j) * A[i])

        return base + ans