Akshay and Teacher (ATCH) Editorial

PROBLEM LINK:

Practice
Contest

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

4 Likes

what will be the output of the given input array
1 2 1 -10 2 3
corresponding subsum array will be
1 3 4 -6 2 5
and sub indices array will be
[[0,0],[0,1],[0,2],[0,3],[4,4],[4,5]]
acc to this output will be 5
but it should be 9
please help me out if i’m getting wrong in the logic as described in the editorial

yes ur right! output would be 5 if we use the above one.