Given an unsorted integer array, find the subarray that has the greatest sum. Return the sum.
Assumptions
The given array is not null and has length of at least 1.
Examples
{2, -1, 4, -2, 1}, the largest subarray sum is 2 + (-1) + 4 = 5
{-2, -1, -3}, the largest subarray sum is -1
class Solution(object):
def largestSum(self, array):
cur_sum = max_sum = array[0]
for num in array[1:]:
cur_sum = max(cur_sum + num,num)
max_sum = max(cur_sum,max_sum)
return max_sum
