I need to solve this problem using this algorathim solve the

I need to solve this problem using this algorathim.

solve the Maximum Subsequence Sum Problem:

Instead of just calculating the sums in two pass, we break down the problem to a smaller one with a strongInduction Hypothesis:

induction hypothesis:We can find SUM(n-1) and TRAILINGSUM(n-1) for any sequence of n – 1 integers. SUM(n-1) is themaximum subsequence sum of an array with n – 1 numbers. TRAILINGSUM(n-1) is the maximum sum ofa subsequence that ends x1, …, xn-1.

Base Case: For n = 1 we have:

SUM(1) = TRAILINGSUM(1) = Max(0, x1)

Induction Step:
SUM(n) = Max ( SUM(n-1) , TRAILINGSUM(n-1)+xn)

TRAILINGSUM(n) = Max(0, TRAILINGSUM(n-1)+xn)

This is the code I need to follow

int RecursiveOnePass_maxSubSum(vector<int> data,int *TrailingSum,int n)

{

if(n==1)
{
//base case
*TraiingSum = data[0];//TRAILINGSUM
return data[0];//SUM
}
else
{
int oldSum = RecursiveOnePass_maxSubSum(data,TrailingSum,n-1);

//int newSum = maximum of oldSum and *TrailingSum+data[n-1];
//*TrailinSum = maximum of zero and *TrailingSum+data[n-1];
return newSum;
}

}

Solution

Hey heres the code in cpp for your algorithm, hoping this is to find maximum contigous sum in array and I didnt get if you are asking for full working code or just to rewrite the recursive code, anyways if you want full working code in cpp post comments.

#include<algorithm>

int Recursive_maxSubSum(vector <int> data,int *trailingSum,int n)

{

if(n==1)

{

//Base conditions

*trailingSum=data[0];

return data[0];

}

else if(n > 1)

{

//Induction steps.

int prevSum=Recursive_maxSubSum(data,trailingSum,n-1)

int currentSum=max(oldSum,*trailingSum+data[n-1]);

trailingSum=max(0,*trailingSum+data[n-1];

return currentSum;

}

}