- The problem here is to find the max sub array from an array, the problem name is max sum subarray! A video that illustrates the problem Link
Brute force simply iterate through diff array sizes then iterate through each element and calculate the sum and just return the max.
def max_sum_subarray(arr):
maxi = float('-Inf')
for poss_size in range(1, len(arr)):
for start_idx in range(poss_size):
if (start_idx + poss_size) > len(arr):
break
sum = 0
for i in range(start_idx+poss_size):
sum += arr[i]
ans = max(maxi,sum)
return ans
Another approach is instead of adding l[i-1] --- l[i-n], we will only add the last element so if we are at index 0 will add value of index 1 and so on
def max_sum_another_app(arr)
ans = float('-Inf')
for start_idx in range(len(arr)):
sum = 0
for poss_size in range(1,len(arr))
if start_idx+poss_size > len(arr):
break
sum += arr[start_idx+poss_size-1] #only add last element
ans = max(ans,sum)
return ans