Maximum Subarray Sum
Medium 40 XPArraysDynamic Programming
Commonly asked at Amazon, Microsoft, Google, LinkedIn
Read a list of integers and print the largest sum of any non-empty continuous subarray.
- Input
- One line of space-separated integers.
- Output
- The maximum subarray sum.
- Constraints
- Up to 100,000 numbers. Aim for O(n).
Sample 1
Input
-2 1 -3 4 -1 2 1 -5 4
Output
6
Explanation: 4 + -1 + 2 + 1 = 6
Read input with input() (no prompt message) and print only the answer. Run tries the Input box; Submit checks all test cases.
Output Loading Python (first time takes a few seconds)
Press Run to see the result here.The solution unlocks after 3 submissions.