Given an array of numbers, calculate the largest sum of all possible blocks of consecutive elements within the array. The numbers will be a mix of positive and negative values. If all numbers of the sequence are nonnegative, the answer will be the sum of the entire array. If all numbers in the array are negative, your algorithm should return zero. Similarly, an empty array should result in a zero return from your algorithm.

```
largestSum([-1,-2,-3]) == 0
largestSum([]) == 0
largestSum([1,2,3]) == 6
```

Easy, right? This becomes a lot more interesting with a mix of positive and negative numbers:

```
largestSum([31,-41,59,26,-53,58,97,-93,-23,84]) == 187
```

The largest sum comes from elements in positions 3 through 7:
```59+26+(-53)+58+97 == 187```

Once your algorithm works with these, the test-cases will try your submission with increasingly larger random problem sizes.

Difficulty: introductory

Starter code:

def largest_sum(arr):
	

Solutions:
def largest_sum(arr):
    sum = max_sum = 0
    for n in arr:
        sum = max(sum + n, 0)
        max_sum = max(sum, max_sum)
    return max_sum

def largest_sum(arr):
    a, b, ar = 0, 0, arr[:]
    for i in ar:
        b+=i
        if b < 0: b = 0
        if b > a: a = b
    return a

def largest_sum(a):
    m = c = 0
    for i in a:
        c = max(0,c+i)
        m = max(m,c)
    return m

def largest_sum(arr):
    current = so_far = 0
    for n in arr:
        current += n
        if current > so_far: so_far = current
        if current <= 0: current = 0
    return so_far

def largest_sum(arr):
    c, m = 0, 0
    for n in arr:
        c = max(0, c + n)
        m = max(m, c)
    return m

def largest_sum(arr):

    largest = 0
    temp = 0

    for num in arr:
        temp += num
        if temp < 0:
            temp = 0
        elif temp > largest:
            largest = temp

    return largest

def largest_sum(arr):
    if len(arr) == 0:
        return 0 
    cache = [arr[0]]
    for i in range(1, len(arr)):
        cache.append(max(arr[i], cache[-1] + arr[i]))
    return 0 if max(cache) < 0 else max(cache)

def largest_sum(arr):
    best_sum = 0
    current_sum = 0
    for item in arr:
        current_sum += item
        if current_sum < 0:
            current_sum = 0
        else:
            if current_sum > best_sum:
                best_sum = current_sum
    return best_sum

def largest_sum(a):
    best_sum = 0 
    current_sum = 0
    for x in a:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

def largest_sum(arr):
    ans,sum = 0,0
    for i in range(len(arr)):
        sum = max(arr[i], arr[i] + sum)
        ans = max(ans,sum)
    return ans