[LintCode]Maximum Subarray Difference

这道题的解法是max subarray，min subarray，max subarray II的结合，不细说了，注意左边要维护两个数组分别是globalMax和globalMin，右边时候同理的，localMax和localMin，DP方程参考之前的题目，时间复杂度O(n)，空间复杂度O(n)，代码如下：

	public class Solution {
	/**
	* @param nums: A list of integers
	* @return: An integer indicate the value of maximum difference between two
	* Subarrays
	*/
	public int maxDiffSubArrays(ArrayList<Integer> nums) {
	if (nums == null)
	return 0;
	int len = nums.size(), currMaxSum = 0, currMinSum = 0;
	int[] leftGlobalMax = new int[len];
	int[] leftGlobalMin = new int[len];
	for (int i = 0; i < len - 1; i++) {
	int localMax = currMaxSum + nums.get(i);
	int localMin = currMinSum + nums.get(i);
	if (i == 0) {
	leftGlobalMax[i + 1] = localMax;
	leftGlobalMin[i + 1] = localMin;
	} else {
	leftGlobalMax[i + 1] = max(localMax, leftGlobalMax[i]);
	leftGlobalMin[i + 1] = min(localMin, leftGlobalMin[i]);
	}
	currMaxSum = max(0, localMax);
	currMinSum = min(0, localMin);
	}
	currMaxSum = 0;
	currMinSum = 0;
	int maxDiff = 0;
	for (int i = len - 1; i > 0; i--) {
	int localMax = currMaxSum + nums.get(i);
	int localMin = currMinSum + nums.get(i);
	int localMaxDiff = max(leftGlobalMax[i] - localMin, localMax - leftGlobalMin[i]);
	maxDiff = max(maxDiff, localMaxDiff);
	currMaxSum = max(0, localMax);
	currMinSum = min(0, localMin);
	}
	return maxDiff;
	}
	private int max(int a, int b) {
	return a >= b? a: b;
	}
	private int min(int a, int b) {
	return a <= b? a: b;
	}
	}

view raw maximum subarray difference.java hosted with ❤ by GitHub