#0055

Maximum Subarray Sum

MediumDSA22 min20 XP

Problem

Given a non-empty list of integers, return the largest sum of any contiguous subarray.

Why This Matters

This problem teaches the DP habit of asking: should the current item extend the previous answer, or start a new answer?

Function Signature

def max_subarray_sum(nums):

Examples

Example 1

Inputnums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output6

The best subarray is [4, -1, 2, 1], whose sum is 6.

Constraints

The input list is non-empty.
Numbers can be negative.
Return the sum, not the subarray.

CodePython

def max_subarray_sum(nums):
    """
    Input example: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    Return: 6
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return 0

def max_subarray_sum(nums):
    """
    Input example: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    Return: 6
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return 0

Visible browser tests run here when available.

Testcases2 visible / 3 hidden categories

Mixed positive and negative values

Input[-2,1,-3,4,-1,2,1,-5,4]

Expected6

The best contiguous run is 4, -1, 2, 1.

All negative values

Input[-8, -3, -6]

Expected-3

The least negative single element is the best subarray.

Hidden Test Categories

Single itemBest subarray at the beginningBest subarray at the end