Maximum sum subarrays.
Find the maximum sum of subarray given an array of n length.
Remove atmost one element to make maximise it further.
The final array should have atleast one element
In this problem, we have been given an array of n length.
The first part involves, finding maximum subarrays ending at each index, which is Kadene’s Algo.
Here, we need to maintain both the maximum sum for arrays ending at an index, and also the range of the resulting subarray
subSum = [nums] subInd = [[0,0]] #kadenes for i in range(1,n): if subSum[-1] + nums[i] >= nums[i]: subSum.append(subSum[-1] + nums[i]) subInd.append([subInd[-1],i]) else: subSum.append(nums[i]) subInd.append([i,i])
Here, we’ve set the condition at ‘>=’ , since we need to get the largest subarray, so that in the end, we can get a more smaller number to reduce.
Now, the next part involves, looping through the subarray indices and checking if the corresponding subarray sum matches the maximum, if it does, we add it to maxIndices,
Note, that here we do need to check that the subarray start and end indices are different, since we need a subarray having size more than 1, else if we remove a single element, the array becomes empty.
Once, we have the maxIndices, we iterate through them, and find the corresponding minimum values in the input array, which is less than 0.
Finally, we subtract this value, from the already max subarray sum.
maxSum = max(subSum) maxInd =  for i in range(len(subInd)): if subSum[i] == maxSum: maxInd.append(subInd[i]) minVal = 0 for i in maxInd: if i != i: temp = min(nums[i:i+1]) if temp < minVal: minVal = temp print(maxSum - minVal)
Part1: Get subSum and subInd, which list the max subarray sum, and indices, ending at that index.
Part2: Compare and find, maximum sum subarray range, and add those indices, if length greater than 1.
Part3: Find the minimum value, less than 0, from the maximum sum subarray ranges.