From ASMBits


The maximum subarray sum algorithm returns the biggest sum of the elements of any subarray of a given array. A subarray consists of consecutive elements of an array (a subarray is not the same as a subsequence).

For example, consider the following array: [ -1, -1, 3, -1, 3, -2 ]

There are many subarrays of this array. A subarray may include the entire array. A subarray cannot be empty. In this example, the subarray that gives the largest sum is [3, -1, 3] (3rd through 5th elements), with a sum of 5.

Write a function that returns the maximum subarray sum for a given array of 32-bit signed words. (This problem doesn't make sense with unsigned words, because if all elements were non-negative, you'd always include all of them to get the biggest sum.)

The function has two parameters. The first parameter is a pointer to the start of the array. The second parameter is the length of the array (at least 1).

You may wish to reuse your solution from arm/arraysum. A O(n3) solution is acceptable here. O(n2) isn't difficult, and O(n) is possible.

Sample Input

[-1, -1, 3, -1, 3, -2]

Sample Output


Write your solution here

Upload a source file...