PROBLEM LINK:
Author: Shivam Pawase
Tester: Nishchith Shetty
Editorialist: Sangram Desai
DIFFICULTY:
EASY
PREREQUISITES:
Maximum sum subarrays.
PROBLEM:
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
EXPLANATION:
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[0]]
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][0],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[0] != i[1]:
temp = min(nums[i[0]:i[1]+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.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here
Tester’s solution can be found here