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