CareerCup

public int maxProfit(int[] prices) {
        int sell = 0, prev_sell = 0;
        int buy = Integer.MIN_VALUE, prev_buy;
        for (int price : prices) {
            prev_buy = buy;
            buy = Math.max(prev_sell - price, prev_buy);
            prev_sell = sell;
            sell = Math.max(prev_buy + price, prev_sell);
        }
        return sell;
    }

public int maxProfit(int[] prices) {
int sell = 0, prev_sell = 0;
int buy = Integer.MIN_VALUE, prev_buy;
for (int price : prices) {
prev_buy = buy;
buy = Math.max(prev_sell - price, prev_buy);
prev_sell = sell;
sell = Math.max(prev_buy + price, prev_sell);
}
return sell;
}

public int maxProfit(int[] prices) {
int sell = 0, prev_sell = 0;
int buy = Integer.MIN_VALUE, prev_buy;
for (int price : prices) {
prev_buy = buy;
buy = Math.max(prev_sell - price, prev_buy);
prev_sell = sell;
sell = Math.max(prev_buy + price, prev_sell);
}
return sell;
}

int main() {
    int a[] = {30,30,15,18,20,25,80};
    int n = sizeof(a)/sizeof(a[0]);
    int profit[n];
    int mn[n];
    mn[n-1] = a[n-1];
    int minVal = a[0];
    profit[0] = 0;
    for(int i=1;i<n;i++) {
        profit[i] = max(profit[i-1],a[i]-minVal);
        minVal = min(minVal,a[i]);
    }
    for(int i=n-2;i>=0;i--) {
        mn[i] = min(mn[i+1],a[i]);
    }

    for(int i=4;i<n;i++) {
        profit[i] = max(profit[i],profit[i-1]);
        for(int j=i-3;j>=1;j--) {
            profit[i] = max(profit[i],(max(a[i]-mn[0], profit[j]+(a[i]-mn[j+2]))));
        }
    }
    for(int i=0;i<n;i++)
        cout<<profit[i]<<" ";
    cout<<profit[n-1]<<endl;
    return 0;
}

int main() {
    int a[] = {30,30,15,18,20,25,80};
    int n = sizeof(a)/sizeof(a[0]);
    int profit[n];
    int mn[n];
    mn[n-1] = a[n-1];
    int minVal = a[0];
    profit[0] = 0;
    for(int i=1;i<n;i++) {
        profit[i] = max(profit[i-1],a[i]-minVal);
        minVal = min(minVal,a[i]);
    }
    for(int i=n-2;i>=0;i--) {
        mn[i] = min(mn[i+1],a[i]);
    }

    for(int i=4;i<n;i++) {
        profit[i] = max(profit[i],profit[i-1]);
        for(int j=i-3;j>=1;j--) {
            profit[i] = max(profit[i],(max(a[i]-mn[0], profit[j]+(a[i]-mn[j+2]))));
        }
    }
    for(int i=0;i<n;i++)
        cout<<profit[i]<<" ";
    cout<<profit[n-1]<<endl;
    return 0;
}

We might want to use DP for this problem because of its subproblem nature for maximum profit.

#include    <iostream>
#include    <stdlib.h>
using namespace std;


int maxProfitRec(int a[],int i,int n) {
    if(i >= n)  return 0;
    int mx1 = maxProfitRec(a,i+1,n);
    return max(mx1, a[i]+maxProfitRec(a,i+2,n));
}
int maxProfit(int a[],int n) {
    int table[n+1];
    table[0] = table[1] = 0;

    for(int i=2;i<=n;i++) {
        int mx = table[i-1];
        for(int j=i-2;j>=0;j--) {
            mx = max(table[j]+a[i-1],mx);
        }
        table[i] = mx;
    }
    return table[n];
}
int main() {
    int a[] = {3,5,2,5,60,12,5,234,5,223,123};
    int n  = sizeof(a)/sizeof(a[0]);

    cout<< "DP Algo :"<<maxProfit(a,n) <<endl;
    cout<< "Rec Algo:"<<maxProfitRec(a,0,n) <<endl;
    return 0;
}

2 pm est :)