Kadane's Algorithm - POTD | 24-Nov-2024

[MuhammadTausif]

Kadane's Algorithm

Link

Difficulty: Medium

Given an integer array arr[]. You need to find the maximum sum of a subarray.

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[] = [-2, -4]
Output: -2
Explanation: The subarray {-2} has the largest sum -2.
Input: arr[] = [5, 4, 1, 7, 8]
Output: 25
Explanation: The subarray {5, 4, 1, 7, 8} has the largest sum 25.

Constraints:

• 1 ≤ arr.size() ≤ 105
• -109 ≤ arr[i] ≤ 104

[MuhammadTausif]

Solved

ans = sum = -1e9

for a in arr:
    sum = max(a, sum+a)
    ans = max(ans, sum)

return ans