lintcode-44. Minimum Subarray

1. 问题描述

Description

Given an array of integers, find the continuous subarray with smallest sum.

Return the sum of the subarray.

The subarray should contain one integer at least.

2. my solution

2.1 我的思路

本题有几个关键点

• 如果数字小于0, 那么必然将其纳入其中, 因为这会使和变小
• 如果数字大于0 , 我们不希望把他纳入其中
  从左到右依次遍历, 记录最小的和minSum和sum, 如果sum大于0 , 那么就将其丢弃, 如果sum<minSum, 那么就把minSum更新

2.2 代码实现

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

2.3 运行结果