Kadane Algorithm

0 min read Tweet this post
algorithm

Given an array arr[], the task is to find the subarray that has the maximum sum and return its sum.

Examples:

Input: arr[] = {2, 3, -8, 7, -1, 2, 3}
Output: 11
Explanation: The subarray {7, -1, 2, 3} has the largest sum 11.


Input: arr[] = {4, -5, 3, -2, 1, 5, -6, 3}
Output: 7
Explanation: The subarray {} has the largest sum 7.
0
Step

Initialize maxEnding = 0, result = 0

0
1
2
3
4
5
6
arr[] =
2
3
-8
7
-1
2
3

Maximum Subarray Sum using Kadane's Algorithm

Simulation inspired by https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

algorithm simulation