Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Maximum Subarray

LeetCode #53Medium
cur = max(nums[i], cur + nums[i]) · Kadane's

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

Asked atAmazonMicrosoftLinkedIn
step 1 / 19
-2
1
-3
4
-1
2
1
-5
4
[0][1][2][3][4][5][6][7][8]
Brute force
▸
1best ← −∞
2for i ← 0 to n − 1:
3    for j ← i to n − 1:
4        best ← max(best, sum(nums[i..j]))
5 
6return best
state
  • n9
  • best−∞

line 1Goal: the largest sum among all CONTIGUOUS subarrays. The brute approach is literal — fix a start i, extend an end j, sum that window, and keep the maximum seen.