Skip to content
Katabench
Try free

Maximum Subarray

Medium About 20 min Free, no account needed

Find the largest sum of any contiguous subarray.

The brief

Given an integer array nums, find the contiguous subarray with the largest sum and return that sum.

  • The subarray must contain at least one element.
  • Values can be negative, so you cannot just sum the whole array.

Examples

  • For nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4], return 6. The contiguous slice [4, -1, 2, 1] has the largest sum. It includes the -1 between 4 and 2 because the elements must be consecutive.
  • For nums = [-3, -1, -2], return -1. The best slice is [-1]. Returning 0 would require choosing an empty slice.

The performance bar

The obvious approach tries every subarray, O(n²). The hidden test uses 200,000 elements, so the quadratic version is too slow. You will need MaxSubarraySum to run in O(n).

Starter code

C#
using System;

public class Solution
{
    // TODO: return the largest sum of any contiguous subarray.
    public long MaxSubarraySum(int[] nums)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Dynamic programming
Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.

Related katas