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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/array/minimum-subarray-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.