C / C++ 20Time: O(N)Space: O(1)

Kadane's Algorithm (Maximum Subarray) in Cpp

Learn and benchmark the Kadane's Algorithm (Maximum Subarray) algorithm in Cpp. Time complexity: O(N), Space complexity: O(1). Includes verified runnable code.

⚡ Key Takeaways

Solves the maximum subarray problem in a single pass O(N) time with O(1) space.
Resets current running sum to 0 whenever it drops below zero.
Works with negative numbers if max is initialized to the first element.

⚠️ Edge Cases & Common PitfallsIf the array contains all negative numbers, initializing max_sum to 0 will incorrectly return 0 instead of the largest negative number.

Terminal Output Preview

● Verified Output

Verified Execution Output

Interactive Code Execution

Edit and run this code live in the editor beside this panel.

Frequently Asked Questions

What is the time complexity of Kadane's Algorithm (Maximum Subarray)?▾

The time complexity is O(N) and space complexity is O(1).

How to implement Kadane's Algorithm (Maximum Subarray) in Cpp?▾

Finds the contiguous subarray within a one-dimensional numerical array which has the largest sum in linear time. Solves the maximum subarray problem in a single pass O(N) time with O(1) space.

What are common gotchas for Kadane's Algorithm (Maximum Subarray)?▾

If the array contains all negative numbers, initializing max_sum to 0 will incorrectly return 0 instead of the largest negative number.

Related Methods & Sandboxes

binary search quick sort kadane algorithm

Terminal

Settings

Appearance & Studio

Settings

Appearance & Studio

⌨️ Keyboard Shortcuts