题目：
给定一个整数数组，找到一个具有最小和的子数组。返回其最小和。
给出数组[1, -1, -2, 1]，返回 -3
子数组最少包含一个数字
解题：
和最大子数组 ,差不多的，动态规划的还是可以继续用的
Java程序：
public class Solution { /** * @param nums: a list of integers * @return: A integer indicate the sum of minimum subarray */ public int minSubArray(ArrayList<Integer> nums) { // write your code int min_ending_here = nums.get(0); int min_so_far = nums.get(0); for (int i=1 ;i< nums.size(); i++){ min_ending_here = Math.min(nums.get(i),nums.get(i) + min_ending_here); min_so_far = Math.min( min_so_far, min_ending_here ); } return min_so_far; } }
总耗时: 2153 ms
Python程序：
class Solution: """ @param nums: a list of integers @return: A integer denote the sum of minimum subarray """ def minSubArray(self, nums): # write your code here min_ending_here = min_so_far = nums[0] for x in nums[1:]: min_ending_here = min(x, min_ending_here + x) min_so_far = min(min_so_far , min_ending_here) return min_so_far
总耗时: 648 ms
lintcode 容易题：Minimum Subarray 最小子数组
原文：http://www.cnblogs.com/theskulls/p/4887548.html
