Can you check my approach please ? :-)


#1

Hello,

Here is the approach I choose:
1- I calculate first the max profit on the range ( 0, n) for the first transaction
2- if the index from step_1 is in range, then I calculate the second profit on the range [index, n[

but it seems that some test cases fail with this approach.
someone could correct me ?

thanks :slight_smile:

here is my code solution:


pair<int, int> getMax(const vector &A, int start, int end)
{
int res =0; int resIdx = 0;
int minA = A[start];
for(int i = start; i < end; i++)
{
if(A[i]- minA > res)
{
res = A[i]- minA;
resIdx = i;
}
minA = min(minA, A[i]);
}
pair<int, int> p(resIdx, res);

return p;

}
int Solution::maxProfit(const vector &A) {
int n = A.size();
if(n==0) return 0;
pair<int, int> res1 = getMax(A, 0, n);

pair<int, int> res2;
if(res1.first < n)
{
    res2 = getMax(A, res1.first+1, n);
}

return res1.second + res2.second;

}


#2

Hi, I am using the same approach. And it does fail on some test cases. Were you able to identify the issue? Thanks


#3

Shouldn’t it fail for cases like :
1 7 2 8 9

you’ll pick 1 and 9, when 1 7 and 2 8 resulted in a high profit