A universal solution handling all k transactions at once in C


  • 0
    int maxProfit(int* prices, int size)
    {
        int k = 2;
        int *holds = (int*)malloc(sizeof(int)*k);
        int *solds = (int*)malloc(sizeof(int)*k);
        memset(solds, 0, sizeof(int)*k);
        for(int i = 0; i < k; i++)
            holds[i] = INT_MIN;
        int cur = 0;
        for(int i=0; i < size; i++)
        {
            cur = prices[i];
            for(int j = 0; j < k; j++)
            {
                holds[j] = MAX(holds[j], (j>0? solds[j-1]:0)-cur); //in each transaction we should try to be as much greedy as possible to make it maximal -> buying means less pay while selling mans getting higher;
                solds[j] = MAX(solds[j], holds[j]+cur);
            }
        }
        return solds[k-1];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.