question

Given a single dimension array, find the sum of the largest contiguous subarray.

ex. largestSubarraySum([31, -41, 59, 26, -53, 58, 97, -93, -23, 84])

returns: 187

Largest subarray starts from 59 and ends with 97

ex. largestSubarraySum([31, -41, 59, 26, -53, 58, 97, -93, -23, 84])

returns: 187

Largest subarray starts from 59 and ends with 97

This problem will require some dynamic programming. Think of how to solve it in O(n)

This is an extremely common technical interview question. Kadane's algorithm is a well known algorithm for solving this exact problem. The algorithm works by scanning through the input array and computing the maximum up to each point in the array.

Note: The algorithm will not work for all negative numbers. Consider using absolute values or other techniques for such problems.

Check here for more information on Kadane's algorithm.

```
```**largestSubarraySum**(int input[])

int maxSoFar = 0;

int maxEndingHere = 0;

**for** (int n = 0; n < input.size(); n++)

maxEndingHere += input[n];

**if** (maxEndingHere < 0)

maxEndingHere = 0;

**else if** (maxSoFar < maxEndingHere)

maxSoFar = maxEndingHere;

**return** maxSoFar;

Note: The algorithm will not work for all negative numbers. Consider using absolute values or other techniques for such problems.

Check here for more information on Kadane's algorithm.