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
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;
}