Kadane's algorithm

Kadane's Algorithm is a popular algorithm used to solve the maximum subarray sum problem efficiently in O(n) time. It finds the largest sum of a contiguous subarray within a one-dimensional array of numbers (both positive and negative).

Practice

• https://leetcode.com/problems/maximum-subarray/description/
• https://infoarena.ro/problema/ssm
• https://cses.fi/problemset/task/1643
• https://cses.fi/problemset/task/1644/
• https://codeforces.com/gym/102961/problem/H

References:

• https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
• https://en.wikipedia.org/wiki/Maximum_subarray_problem
• https://www.interviewbit.com/blog/maximum-subarray-sum/
• https://codeforces.com/blog/entry/13713