Maximum Subarray Difference

Given an array with integers.

Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest.

Return the largest difference.

Example

For [1, 2, -3, 1], return 6.

Solution

leftmin - right[i+1] max

leftmax- right[i+ 1] min,

don't do left[i + 1] and make sure right is i + 1

we need to create 4 arary here.

class Solution:
    """
    @param nums: A list of integers
    @return: An integer indicate the value of maximum difference between two
             Subarrays
    """
    def maxDiffSubArrays(self, nums):
        # write your code here
        total = 0 
        n = len(nums)
        p1max = [0] * n
        p2max = [0] * n
        p1min = [0] * n
        p2min = [0] * n

        self.getMaxSubArrays(nums, p1max, p2max)
        self.getMinSubArrays(nums, p1min, p2min)


        for i in range(n - 1):
            total = max(total, abs(p1max[i] - p2min[i + 1]), abs(p1min[i] - p2max[i + 1]))
        return total

    def getMaxSubArrays(self, nums, p1max, p2max):
        n = len(nums)
        maxSum = sys.maxsize * -1 
        sum, minSum = 0, 0 
        for i in range(n):
            sum += nums[i]
            maxSum = max(maxSum, sum - minSum)
            minSum = min(minSum, sum)
            p1max[i] = maxSum
        maxSum = sys.maxsize * -1
        sum, minSum =0, 0
        for i in range(n - 1, -1, -1):
            sum += nums[i]
            maxSum = max(maxSum, sum - minSum)
            minSum = min(minSum, sum)
            p2max[i] = maxSum

    def getMinSubArrays(self,nums, p1min, p2min):
        n = len(nums)
        minSum = sys.maxsize
        sum, maxSum =0, 0
        for i in range(n):
            sum += nums[i]
            minSum = min(minSum, sum - maxSum)
            maxSum = max(maxSum, sum)
            p1min[i] = minSum
        minSum = sys.maxsize
        sum, maxSum = 0, 0
        for i in range(n - 1, -1, -1):
            sum += nums[i]
            minSum = min(minSum, sum - maxSum)
            maxSum = max(maxSum, sum)
            p2min[i] = minSum