# 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:**&#x20;

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来表示就是(在循环中)：

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

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

```java
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

```java
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];
```

```java
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

```java
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;
    }
}
```