# Problem Definition

## Description

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

**Example:**

```plaintext
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
```

**Follow up:**

If you have figured out the O(*n*) solution, try coding another solution using the divide and conquer approach, which is more subtle.

## Notes

1. [Geeks for Geeks - Longest Subarray of non-negative Integers](https://www.geeksforgeeks.org/longest-subarray-non-negative-integers/)
1. Similar to "Best Time to Buy and Sell Stocks 1"
1. [LeetCode discussion - DP solution & some thoughts](https://leetcode.com/problems/maximum-subarray/discuss/20193/DP-solution-and-some-thoughts)
1. [LeetCode discussion - Accepted O(n) solution in java](https://leetcode.com/problems/maximum-subarray/discuss/20211/Accepted-O(n)-solution-in-java)
1. [Dynamic Programming – Kadane’s Algorithm](http://theoryofprogramming.com/2016/10/21/dynamic-programming-kadanes-algorithm/)