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.
- For
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4], return6. The contiguous slice[4, -1, 2, 1]has the largest sum. It includes the-1between4and2because the elements must be consecutive. - For
nums = [-3, -1, -2], return-1. The best slice is[-1]. Returning0would require choosing an empty slice.
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
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.
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
Related katas
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.
- Coin Change II (Count the Ways) Medium Free How many coin combinations make the amount?
- Decode Ways Medium Free How many letter strings could this digit string encode?
- House Robber II (Circular Street) Medium Free The street is a circle now - the first and last houses are neighbors.