## contiguous subarray with largest sum in an array (Maximum Subarray)

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Thoughts:
For each element in the array, we want to track the subarray with the largest sum ending here. And the largest of those largest sums is the result we need. So how do we track the largest sum ending at a particular position? We can keep adding up positive numbers. We can also add negative numbers as long as the sum would be less than 0. If it’s smaller than 0, we need to reset from this position by starting the sum from 0. In the above example, the largest sums ending at each position are [-2,1,-3,4,3,5,6,1,5]. Hence the largest sum is 6.

code (Java):

```public class Solution {
public int maxSubArray(int[] A) {
int maxSumSoFar = Integer.MIN_VALUE;
int maxSumEndingHere = 0;

for(int num : A) {
maxSumEndingHere = Math.max(maxSumEndingHere + num, num);
maxSumSoFar = Math.max(maxSumSoFar, maxSumEndingHere);
}

return maxSumSoFar;
}
}

Code (C++):
class Solution {
public:
int maxSubArray(int A[], int n) {
int maxSumSoFar = INT_MIN;
int maxSumEndingHere = 0;
for(int i = 0; i < n; ++i) {
maxSumEndingHere = max(maxSumEndingHere+A[i], A[i]);
maxSumSoFar = max(maxSumSoFar, maxSumEndingHere);
}
return maxSumSoFar;
}
};

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2de9e14f19c', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2de9e14f1c6',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2de9e14f1c8',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});