> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/array/maximum_subarray_sum.md).

# Maximum Subarray Sum

<http://www.lintcode.com/en/problem/maximum-subarray/>

## Question

> Given an array of integers, find a contiguous subarray which has the largest sum.
>
> Example
>
> Given the array \[−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray \[4,−1,2,1] has the largest sum = 6.

## Analysis

DP和Greedy均可进行求解，不过还是更推荐使用DP，因为Greedy很多情况下都是不正确的。

Dynamic Programming:

```java
maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i];
```

Kadane's Algorithm

## Solution

Brute-force Compare all subarray sum (119 ms 2.49% AC)

```java
// Compare all subarray sum: O(n^2)
class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int sum;
        for (int i = 0; i < nums.length; i++) {
            sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                maxSum = Math.max(sum, maxSum);
            }
        }
        return maxSum;
    }
}
```

Improvement O(n) (7ms 93.68% AC)

```java
class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = sum > 0 ? nums[i] + sum : nums[i];
            maxSum = Math.max(maxSum, sum);
        }
        return maxSum;
    }
}
```

Dynamic Programming

```java
// Dynamic Programming: O(n)
// Similar idea to Greedy Algorithm

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] A) {
        int n = A.length;
        int[] dp = new int[n]; //dp[i] means the maximum subarray ending with A[i];
        dp[0] = A[0];
        int max = dp[0];

        for(int i = 1; i < n; i++){
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}
```

Greedy Algorithm

```java
// Greedy Algorithm: O(n)
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum = sum + nums[i];
            max = Math.max(sum, max);
            sum = Math.max(sum, 0);
        }
        return max;
    }
}
```

Prefix Sum

```java
public class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;

        int max = Integer.MIN_VALUE, min = 0;
        int prefixSum = 0;
        for(int i = 0; i < nums.length; i++){
            prefixSum += nums[i];
            max = Math.max(max, prefixSum - min);
            min = Math.min(min, prefixSum);
        }

        return max;
    }
}
```

Kadane's Alogrithm

```java
public class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;

        int cur = nums[0];
        int max = nums[0];
        for(int i = 1; i < nums.length; i++){
            cur = Math.max(nums[i], cur + nums[i]);
            max = Math.max(max, cur);
        }

        return max;
    }
}
```

## Related Problems

Maximum Subarray II

Maximum Subarray III

Maximum Subarray IV

## Reference

* [LeetCode: DP Solution & Some Thoughts](https://leetcode.com/problems/maximum-subarray/discuss/20193/DP-solution-and-some-thoughts)
* [programcreek: Maximum Subarray (Java)](http://www.programcreek.com/2013/02/leetcode-maximum-subarray-java/)
* [O(n^3) algorithm](https://gist.github.com/mycodeschool/9666221e7527935d8e1d)
* [O(n^2) algorithm](https://gist.github.com/mycodeschool/447854ea1844b1b42cd3)
* [O(NlogN) algorithm](https://gist.github.com/mycodeschool/8b4bcff69427c8a6f2aa)
* [O(N) algorithm](https://gist.github.com/mycodeschool/4b0b01e1d08932066301)
* [Video Tutorial](https://www.youtube.com/watch?v=ohHWQf1HDfU)
* [Evolve from brute force to optimal](https://leetcode.com/problems/maximum-subarray/discuss/20294/Evolve-from-brute-force-to-optimal-a-review-of-all-solutions)
* Wikipedia: <https://en.wikipedia.org/wiki/Maximum_subarray_problem>