Minimum Subarray

http://www.lintcode.com/en/problem/minimum-subarray/

class Solution {
public:
    /**
     * @param nums: a list of integers
     * @return: A integer denote the sum of minimum subarray
     */
    int minSubArray(vector<int> nums) {
        // write your code here
        if(nums.empty()) return 0;
        int result = nums[0];
        int localmin = nums[0];
        for(int i=1; i<nums.size(); i++) {
            localmin = min(nums[i], localmin+nums[i]);
            if(localmin < result) 
                result = localmin;
        }
        return result;
    }
};

另一种写法：

int minSubArray(vector<int> nums) {
        int local = 0;
        int global = INT_MAX;
        //local is 0 if it's larger than 0 after counting current value
        //update globla first
        for(auto const& val : nums) {
            global = min(global, local+val);
            local = min(0, local + val);
        }
        return global;
    }
`