0
LearnArrays

Maximum Subarray (Kadane)

Read the lesson → understand the pattern → then code. Tutor works offline (built-in teacher); optional Cursor/Gemini keys upgrade chat quality.

Topic refresher: Arrays — Index Thinking

Treat every array problem as: What do I know at index i? What must I remember from the past?

// Running best pattern
int best = nums[0];
for (int i = 1; i < n; i++) {
    // update state using nums[i]
    best = max(best, candidate);
}
return best;
Arrays

Maximum Subarray (Kadane)

Medium
LeetCode
7/14
MediumArraysLeetCode #53

Kadane's Algorithm

At each index: extend the previous subarray or start fresh?

cur = max(x, cur+x), ans = max(ans, cur).

Examples

Example 1

Input

9
-2 1 -3 4 -1 2 1 -5 4

Output

6
Example 2

Input

1
1

Output

1

Stuck? Take a nudge

C++17