# Minimum Subarray

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时，都保证以当前元素作为最后一个元素。

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

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

#### Approach 2 - Prefix Sum

• 当前 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;
}
}
``````