[LintCode] Minimum Subarray

Question

link

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

Note The subarray should contain at least one integer.

Example For [1, -1, -2, 1], return -3

Analysis

Same as “Max subarray”.

Code

public int minSubArray(ArrayList<Integer> nums) {
    // write your code
    if (nums == null || nums.size() == 0) {
        return 0;
    }
    int min = nums.get(0);
    int pre = Math.min(0, nums.get(0));
    for (int i = 1; i < nums.size(); i++) {
        pre += nums.get(i);
        min = Math.min(min, pre);
        pre = Math.min(0, pre);
    }
    return min;
}