# 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>


---

# 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/maximum_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.