My O(nk) greedy implement, why is it so slow?


  • 0
    H

    class Solution {
    public:
    int maxProfit(int k, vector<int> &prices) {
    int ans=0,sz=prices.size(),x,y,Max,Min;
    if (sz<2) return 0;
    bool *use=new bool[sz]{0};
    bool flag;
    if (k>sz/2) k=sz/2;
    while (k--)
    {
    x=y=Max=Min=-1;
    flag=0;
    for (int i=0;i<sz;i++)
    if (!use[i])
    {
    if (flag==0)
    {
    if (Min==-1||prices[i]<prices[Min]) Min=i;
    if (y==-1||prices[i]-prices[Min]>prices[y]-prices[x]) x=Min,y=i;
    }
    else
    {
    if (Max==-1||prices[i]>prices[Max]) Max=i;
    if (y==-1||prices[Max]-prices[i]>prices[y]-prices[x]) x=i,y=Max;
    }
    }
    else
    {
    flag^=1;
    Max=Min=-1;
    }
    if (prices[y]-prices[x]>0) ans+=prices[y]-prices[x];
    else return ans;
    use[x]=use[y]=1;
    }
    return ans;
    }
    };


  • 0
    L

    It's a disaster to read your code if you don't follow instruction and paste your code in the proper way.


Log in to reply
 

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