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
Top comments (0)