Algorithm

LintCode/Maximum Subarry II; Maximum Subarray Difference

Problem Summary

Problem 1: Maximum Subarray II

Given an array of integers, find two non-overlapping subarrays which have the largest sum. The subarray should contain at least one number and the numbers in each subarray should be contiguous.

Problem 2: Maximum Subarray Difference

Given an array of integers, find two non-overlapping subarrays A and B, such that |SUM(A) - SUM(B)| is the largest.
The subarray should contain at least one number and the numbers in each subarray should be contiguous.
Calculate the largest difference.

Solution

Problem 1:

Let us denote the given array with A[0]A[1]…A[N-1].
Define

  1. f[i] as the maximal sum of subarray ending at i or before i,
  2. g[i] as the maximal sum of two subarrays of which the second one ends at i.

So the answer is max{g[i]}, i = 0,1,…,N-1.

If we use min_sum to indicate the minimum cumulative sum before i, we have

f[i] = max{f[i-1], cur_sum - min_sum}
g[i] = max{g[i-1], f[i-1]} + A[i]

The time complexity is O(N); the space complexity is O(1), since we only need f[i-1] and g[i-1], instead of f[0]…f[i-1] and g[0]…g[i-1], when we calculate f[i] and g[i].

Problem 2:

This is easier after we solved problem 1.

Define

  1. f[i][0] as the maximal sum of subarray ending at i or before i,
  2. f[i][1] as the minimal sum of subarray ending at i or before i,
  3. g[i][0] as the maximal difference of two subarrays of which the second one ends at i.
  4. g[i][1] as the minimal difference of two subarrays of which the second one ends at i.

So the answer is max{abs(g[i][j])}, i = 0,1,…,N-1, j = 0,1.

We have

f[i][0] = max{f[i-1][0], cur_sum - min_sum}
f[i][1] = min{f[i-1][1], cur_sum - max_sum}
g[i][0] = max{g[i-1][0], -f[i-1][1]} + nums[i-1];
g[i][1] = min{g[i-1][1], -f[i-1][0]} + nums[i-1];

The time complexity is O(N); the space complexity is O(1).

Code 1: Maximum Subarray II, O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    int maxTwoSubArrays(vector<int> &nums) {
        int n = nums.size();
        if (n<2)
        	return 0;
        int f[2], g[2], sum = 0, min_sum = 0, ans = INT_MIN;
        f[0] = g[0] = INT_MIN/2;
        int flag = 1;
        for (int i = 1; i <= n; ++i)
        {
        	sum += nums[i-1];
        	f[flag] = max(f[1-flag],sum - min_sum);
        	min_sum = min(min_sum,sum);
        	g[flag] = max(g[1-flag],f[1-flag]) + nums[i-1];
        	ans = max(ans,g[flag]);
            flag = 1-flag;
        }
        return ans;
    }
};

Code 2: Maximum Subarray II, O(N) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    int maxTwoSubArrays(vector<int> &nums) {
        int n = nums.size();
        if (n<2)
        	return 0;
        int f[n+2], g[n+2], sum = 0, min_sum = 0, ans = INT_MIN;
        f[0] = g[0] = INT_MIN/2;
        for (int i = 1; i <= n; ++i)
        {
        	sum += nums[i-1];
        	f[i] = max(f[i-1],sum - min_sum);
        	min_sum = min(min_sum,sum);
        	g[i] = max(g[i-1],f[i-1]) + nums[i-1];
        	ans = max(ans,g[i]);
        }
        return  ans;
    }
};

Code 3: Maximum Subarray Difference

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: An integer indicate the value of maximum difference between two substrings
     */
    int maxDiffSubArrays(vector<int> &nums) {
    	int n = nums.size();
    	int f[n+2][2],g[n+2][2];
    	f[0][0] = g[0][0] = INT_MIN;
    	f[0][1] = g[0][1] = INT_MAX;
    	int sum = 0, min_sum = 0, max_sum = 0, ans = 0;
    	for (int i = 1; i <= n; ++i)
    	{
    		sum += nums[i-1];
    		f[i][0] = max(f[i-1][0],sum - min_sum);
    		f[i][1] = min(f[i-1][1],sum - max_sum);
    		min_sum = min(sum,min_sum);
    		max_sum = max(sum,max_sum);
    		g[i][0] = max(g[i-1][0], -f[i-1][1]) + nums[i-1];
    		g[i][1] = min(g[i-1][1], -f[i-1][0]) + nums[i-1];
    		if (i>1)
    		{
    			ans = max(abs(g[i][0]), ans);
    			ans = max(abs(g[i][1]), ans);
    		}
    	}
    	return ans;
    }
};