Maxsub algorithm in the textbook is to find the subarray whose sum is the maximum. Similarly, you can modify it to Minsub algorithm to find the subarray whose sum is the minimum.

1. By modify the MaxsubFastest algorithm, write the MinsubFastest so that it uses only a single loop and, instead of computing n+1 different Mt values, it maintains just a single variable M for Mts.

Original Algorithm:

for t 1 to n do

Mt max{0, Mt -1 + A[t]}

m 0

for t 1 to n do

m max{m, Mt }

2. Modify the MinsubFastest algorithm so that it returns both the value of the minimum subarray summation and the indices j and k that identify the minimum subarray A[j : k], i.e. a triplet of ( value of the minimum subarray summation, i, j ). The running time of your algorithm should be O(n).

3. Implement your MinsubFastest(A) algorithm in 2) in Python, printing a triplet of three values.