Kadane Algorithm

A C++ implementation of Kadane's Algorithm to efficiently find the Maximum Sum Subarray in linear time.

Features

• Finds the maximum subarray sum
• Prints the elements of the maximum subarray
• Time Complexity: O(n)
• Space Complexity: O(1)

Technologies

• C++
• STL (vector)

Usage

Compile:

g++ kadane.cpp -o kadane

Run:

./kadane

Example

Input

8
-2 -3 4 -1 -2 1 5 -3

Output

Maximum Subarray Sum: 7
Subarray:
4 -1 -2 1 5

Learning Outcomes

• Dynamic Programming
• Kadane's Algorithm
• Algorithm Optimization

Author

Yazeed Alruzieh