Maximum Subarray Problem | Dataford Interview Questions

Find maximum sum for any contiguous subarray in array. arr = [-1,3,4,-2,5,-7]; the highest value contiguous subarray runs from arr[1]-arr[4] and is 3 + 4 + -2 + 5 = 10.

Asked in the Phone interview stage. Algo question in Python.

Function

Write a function that returns the maximum sum of any contiguous subarray.

Input

arr: a list of integers

Output

Return a single integer, the maximum contiguous subarray sum.

Constraints

1 <= len(arr) <= 10^5
-10^9 <= arr[i] <= 10^9
The answer fits in a 64-bit signed integer

Function Signature

def max_subarray_sum(arr):

Your question is Maximum Subarray Problem. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem