Minimum Subarray Sum

https://www.lintcode.com/problem/minimum-subarray/description

Description

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

Return the sum of the subarray.

Note:

The subarray should contain one integer at least.

Example

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

Analysis

Approach 1 - Kadane's Algorithm

Maximum Subarray Sum和Minimum Subarray Sum的思路完全一样，只是max 和 min的区别。在各种讨论和解题报告中，常出现一个算法：Kadane's Algorithm。

Kadane's Algorithm 其实是在维护一个sliding window，每一次变化这个window时，都保证以当前元素作为最后一个元素。

这个sliding window的起点不确定，但是终点是current元素，因而是一个local最优解，因此需要每次迭代中去比较local最优解和全局global最优解，从而更新global最优解。

用DP来表示就是(在循环中)：

dp[i] = Math.min(dp[i - 1] + nums.get(i), nums.get(i));
minSum = Math.min(dp[i], minSum);

不过也完全不用开辟一个dp[]数组:

cur = Math.min(prevMin + nums.get(i), nums.get(i));
minSum = Math.min(minSum, cur);
prevMin = cur;

Approach 2 - Prefix Sum

此外还有一种思路是利用prefix sum，前缀和：

对于每一个位置 i ，我们维护

• 当前 prefix sum；

• subarray 最小 prefix sum

• subarray 最大 prefix sum

Solution

Kadane's Algorithm - O(1) space, O(n) time

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: A integer indicate the sum of minimum subarray
     */
    public int minSubArray(ArrayList<Integer> nums) {
        if (nums == null || nums.size() == 0) {
            return 0;
        }

        int size = nums.size();
        int min = Integer.MAX_VALUE;
        int prevMin = nums.get(0), minSum = nums.get(0);
        int cur = 0;
        for (int i = 1; i < size; i++) {
            cur = Math.min(prevMin + nums.get(i), nums.get(i));
            prevMin = cur;
            minSum = Math.min(minSum, cur);
        }
        return minSum;
    }
}

Dynamic Programming - 其中dp[i] 代表以i最为结尾的子数组中最小的和Sum，本质上还是Kadane's Algorithm。

// dp[i] means the maximum subarray ending with A[i];

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: A integer indicate the sum of minimum subarray
     */
    public int minSubArray(ArrayList<Integer> nums) {
        if (nums == null || nums.size() == 0) {
            return 0;
        }

        int size = nums.size();
        int[] dp = new int[size];
        dp[0] = nums.get(0);
        int minSum = dp[0];
        for (int i = 1; i < size; i++) {
            dp[i] = Math.min(dp[i - 1] + nums.get(i), nums.get(i));
            minSum = Math.min(dp[i], minSum);
        }
        return minSum;
    }
}

Prefix Sum Approach

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 max = 0, min = Integer.MAX_VALUE;
        int prefixSum = 0;
        for(int i = 0; i < nums.size(); i++){
            prefixSum += nums.get(i);
            min = Math.min(min, prefixSum - max);
            max = Math.max(max, prefixSum);
        }

        return min;
    }
}