Akshay and Teacher (ATCH) Editorial

dynamic-programming
kjsce
maximum-sum
short-contest

#1

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