# 53. Maximum Subarray (Easy)

https://leetcode.com/problems/maximum-subarray/

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

Example:

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

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

## Solutions

``````class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;

// 'sum' is the summation of prior values if sum > 0
// take it as a single element
int sum = 0;
for (int i = 0; i < nums.length; i++) {
// sum < 0, prior elements are useless since they exert an adverse impact on max summation
if (sum < 0) {
sum = 0;
}

sum += nums[i];

// set the max to sum, max is a global variable, by contrast, sum is a contextual variable
// which is concerning elements prior to current element
if (sum > max) {
max = sum;
}
}

return max;
}
}
``````