题目：
给定一个整数数组，找到一个具有最小和的子数组。返回其最小和。
样例
给出数组[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
上面的空间复杂度是O(1),定义一个数组dp[i] ，表示当前i位置时候的最小子数组的值，最后再变量找出dp的最小值就是答案。
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
if( nums == null)
return 0;
int n = nums.size();
int dp[] = new int[n];
dp[0] = nums.get(0);
for(int i=1;i<n;i++){
int tmp = dp[i-1] + nums.get(i);
if(tmp > nums.get(i))
dp[i] = nums.get(i);
else
dp[i] = tmp;
}
int Min = Integer.MAX_VALUE;
for(int i =0;i< n;i++){
if(dp[i] < Min)
Min = dp[i];
}
return Min;
}
}
Java Code
总耗时: 2556 ms