Kadanes Algorithm

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