最小子数组

题目

给定一个整数数组,找到一个具有最小和的子数组。返回其最小和。http://www.lintcode.com/zh-cn/problem/minimum-subarray/

分析

这是最大子数组的逆命题, http://www.hoyt-tian.com/zui-da-zi-shu-zu/,解题思路也是类似,逆转即可,最近连做好几道这样的问题。

代码


public class Solution {
    /*
     * @param nums: a list of integers
     * @return: A integer indicate the sum of minimum subarray
     */
    public int minSubArray(List nums) {
        // write your code here
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for(int i=0; i < nums.size(); i++){
            sum += nums.get(i).intValue();
            if(sum < min) min = sum;
            if(sum > 0) sum = 0;
        }
        return min;
    }
}
Show Comments

Get the latest posts delivered right to your inbox.