Section titled Maximum%20Subarray%20Sum%20%u2013%20Kadane%u2019s%20Algorithm
Maximum Subarray Sum – Kadane’s Algorithm
Section titled Description
Description
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/