1
class Solution(object):
2
    def maxValueAfterReverse(self, nums):
3
        """
4
        :type nums: List[int]
5
        :rtype: int
6
        """
7
        # basic idea without fancy stuff
8
        # 1. https://leetcode.com/problems/reverse-subarray-to-maximize-array-value/discuss/489929/O(n)-time-O(1)-space.-In-depth-Explanation
9
        # 2. https://code.dennyzhang.com/reverse-subarray-to-maximize-array-value
10

11
        # This can be done in three steps each step taking O(N) time
12

13
        res, n = 0, len(nums)
14

15
        # Step 1: Assume that no subarray is reversed and so the sum would just accumulate over all the abs differences
16
        for index in range(1, n):
17
            res += abs(nums[index] - nums[index - 1])
18

19
        # Step 2: Reversing the left or the right half so basically this idea stems from prefix array type question where in which we have the sum upto ith index but then to get at a specific index we substract extra sum, following from that idea. Or refer to the reference 1
20

21
        diff = 0
22
        for index in range(n):
23

24
            # reversing from 0th index to current
25
            if index + 1 < n:
26
                diff = max(
27
                    diff,
28
                    abs(nums[index + 1] - nums[0]) - abs(nums[index + 1] - nums[index]),
29
                )  # diff between 0 and curr - diff curr and curr + 1
30

31
            # reversing from current to last index n - 1
32
            if index > 0:
33
                diff = max(
34
                    diff,
35
                    abs(nums[index - 1] - nums[n - 1])
36
                    - abs(nums[index - 1] - nums[index]),
37
                )
38

39
        # Step 3: We still need to check the middle reverse part, we can do this using the min max trick
40
        low_number, high_number = float("inf"), float("-inf")
41

42
        for index in range(n - 1):
43

44
            low_number = min(
45
                low_number, max(nums[index], nums[index + 1])
46
            )  # min of low and the max of the current and next number
47
            high_number = max(high_number, min(nums[index], nums[index + 1]))
48

49
            diff = max(
50
                diff, 2 * (high_number - low_number)
51
            )  # This is explained in ref 1
52

53
        return res + diff