[LintCode]Minimum Subarray

和max subarray是类似的题目，divide and conquer的方法是类似的，我们写一下DP的方法，我们只需要稍微改变一下DP方程就可以了：

• localMin[i] = min(localMin[i - 1] + A[i], A[i]);
• globalMin[i] = min(globalMin[i - 1], localMin[i]);

时间复杂度O(n), 空间复杂度可以优化到O(1)，代码如下：

	public class Solution {
	/**
	* @param nums: a list of integers
	* @return: A integer indicate the sum of minimum subarray
	*/
	public int minSubArray(ArrayList<Integer> nums) {
	if (nums == null)
	return 0;
	int len = nums.size();
	int min = Integer.MAX_VALUE, currSum = 0;
	for (int i = 0; i < len; i++) {
	int localMin = currSum + nums.get(i);
	min = localMin < min? localMin: min;
	currSum = localMin >= 0? 0: localMin;
	}
	return min;
	}
	}

view raw minimum subarray.java hosted with ❤ by GitHub