Maximum Subarray Difference

Description:

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

Note

The subarray should contain at least one number

Solution:

( 不难证明这两个子数组必然是紧邻的 )

class Solution { public: /** * @param nums: A list of integers * @return: An integer indicate the value of maximum difference between two * Subarrays */ int maxDiffSubArrays(vector<int> nums) { auto sz = (int)nums.size(); if (sz == 0) return 0; vector<int> minl(sz, nums[0]); vector<int> maxl(sz, nums[0]); vector<int> minr(sz, nums[sz-1]); vector<int> maxr(sz, nums[sz-1]); for (int i = 1; i < sz; ++i) { minl[i] = min(minl[i-1]+nums[i], nums[i]); maxl[i] = max(maxl[i-1]+nums[i], nums[i]); minr[sz-1-i] = min(minr[sz-i]+nums[sz-1-i], nums[sz-1-i]); maxr[sz-1-i] = max(maxr[sz-i]+nums[sz-1-i], nums[sz-1-i]); } int rc = 0; for (int i = 0; i < sz-1; ++i) rc = max(max(rc, maxr[i+1]-minl[i]), maxl[i]-minr[i+1]); return rc; } };

转载于:https://www.cnblogs.com/deofly/p/maximum-subarray-difference.html

相关资源：JAVA上百实例源码以及开源项目