This content originally appeared on DEV Community and was authored by Luckshvadhan B
Approach:
Step 1 Take the array
Step 2 Keep two variables current_sum and max_sum
Step 3 Add each element to current_sum
Step 4 If current_sum becomes less than element reset it
Step 5 Update max_sum
Why this works???
If sum becomes smaller than current element
no use carrying previous sum
so restart from current element
Code:
def maxSubArray(arr):
current_sum = arr[0]
max_sum = arr[0]
for i in range(1, len(arr)):
current_sum = max(arr[i], current_sum + arr[i])
max_sum = max(max_sum, current_sum)
return max_sum
Limitation:
Does not give subarray
only gives sum
This content originally appeared on DEV Community and was authored by Luckshvadhan B
Luckshvadhan B | Sciencx (2026-03-20T15:00:48+00:00) Kadanes Algorithm. Retrieved from https://www.scien.cx/2026/03/20/kadanes-algorithm/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.