Transform the problem to a more solvable one

5154. Reverse Subarray To Maximize Array Value

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        bases = [abs(a-b) for a,b in zip(nums, nums[1:])]
        delta = -float('inf')
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)-1):
                if i==0:
                    this_delta = abs(nums[i]-nums[j+1])-bases[j]
                else:
                    this_delta = abs(nums[i-1]-nums[j])+abs(nums[i]-nums[j+1])-bases[i-1]-bases[j]
                delta = max(delta, this_delta)
        return sum(bases)+delta

Above the naive O(n²) solution will get TLE

11 / 16 test cases passed.Status:Time Limit Exceeded

c++ code from hank55663

100 ms

class Solution {
public:
    int maxValueAfterReverse(vector<int>& nums) {
        int sum=0;
        vector<int> l,r;
        for(int i =0;i<nums.size()-1;i++){
            sum+=abs(nums[i]-nums[i+1]);
            l.push_back(min(nums[i],nums[i+1]));
            r.push_back(max(nums[i],nums[i+1]));
        }
        sort(l.begin(),l.end());
        sort(r.begin(),r.end());
        int Max=max((l.back()-r[0])*2,0);
        for(int i = 1;i<nums.size();i++){
            Max=max(Max,abs(nums[i]-nums[0])-abs(nums[i]-nums[i-1]));
        }
        for(int i =0;i<nums.size()-1;i++){
             Max=max(Max,abs(nums[i]-nums.back())-abs(nums[i+1]-nums[i]));
        }
        return sum+Max;
    }
};

python lee215

480 ms

def maxValueAfterReverse(self, A):
        total = res = sum(abs(a - b) for a, b in zip(A, A[1:]))
        max2, min2 = sorted(A[:2])
        for a, b in zip(A, A[1:]):
            res = max(res, total - abs(a - b) + abs(A[0] - b))
            res = max(res, total - abs(a - b) + abs(A[-1] - a))
            res = max(res, total + (min(a, b) - min2) * 2)
            res = max(res, total + (max2 - max(a, b)) * 2)
            min2, max2 = min(min2, max(a, b)), max(max2, min(a, b))
        return res

Several nice explanations can be found:

Python O(n) - LeetCode Discuss

396. Rotate Function

Rotate Function - LeetCode

suppose at a point i the array is A[0], A[1], A[2], A[3],…, A[k-1], A[k] then we have :

f(i)          = 0 * A[0] + 1 * A[1] + 2 * A[2] + .... +  (k-1) * A[k-1] + k * A[k]
  f(i+1)        = 1 * A[0] + 2 * A[1] + 3 * A[2] + ...  +     k  * A[k-1] + 0 * A[k] 
=>f(i+1) - f(i) =     A[0]   +   A[1]   +   A[2] + ...  +       A[k-1]    - k * A[k] 
   = (A[0]   +   A[1]   +   A[2] + ...  +       A[k-1] + k * A[k]) - (k+1) * A[k]
   = sum(Array) - A[k] * array.length
=> f(i+1) = f(i) + sum(Array) -  last element * array.length

Code can be found here

class Solution:
    def maxRotateFunction(self, A: List[int]) -> int:
        S, L = sum(A), len(A)
        res = f = sum(i*a for i, a in enumerate(A))
        for i in range(1, len(A)):
            f1 = f + S -len(A)*A[L-i]
            f = f1
            res = max(res, f1)
        return res

483. Smallest Good Base

Java solution with hand-writing explain - LeetCode Discuss