Give efficient algorithm along with running time analysis to

Give efficient algorithm along with running time analysis to find the minimum subsequence (Assume the minimum sum is either 0 or a negative value)

Solution

To find the minimum subsequence sum we can use the Kadane\'s algorithm. Actually Kandane\'s algorithm is besically use to find the maximum subsequence but we can modify it to find the minimum subsequence sum.

Here is the Pseudocode of Kadane’s algorithmto find Minimum subarray-

First of all assume that P be an array of intergers.

// Initialization part

minimum_Sum = infinity, L_min = 0, R_min = 0, Min_current = 0, left = 0, right = 0;

//L_min means that leftminimum and R_min means that right minimum//

for (x = 0 to P.length - 1)

Min_current += P[x];

if Min_current < minimum_Sum // Condition to proceed in execution

minimum_Sum = Min_current;

right = x;

L_min = left;

R_right = right ;

if Min_current > 0

Min_current=0;

right = x + 1;

// P[L_min......R_min] is the minimum subsequence sum.

return minimum_Sum;

This minimum_sum is the desired minimum subsequence sum.

Time Analysis: We can see that in the above we have only one for loop and for that for loop the complexity is o(n).

Total complexity = o(n) + Integer = o(n).

left = x + 1;
right = x + 1; // P[L_min......R_min] is the minimum subsequence sum. return minimum_Sum; This minimum_sum is the desired minimum subsequence sum. Time Analysis: We can see that in the above we have only one for loop and for that for loop the complexity is o(n). Total complexity = o(n) + Integer = o(n).