O(n) C Soution in 4 ms with O(1) space


  • 0
    R
    Here maximum profit can be found by finding continuous increasing price seq and then adding the diff of first and last price in the final profit.
    int maxProfit(int* p, int pS) {
        int i, min=p[0], prof=0;
        for(i=1; i<pS; i++)
            if(p[i]>p[i-1])
                continue;	// seq is increasing so continue
            else
            {	// increasing seq is broken, find profit till now and add to profit
                prof += p[i-1]-min;
                min = p[i];
            }
        return prof + p[i-1]-min; // last increasing seq was not added in the loop thus add it here while returning
    }

Log in to reply
 

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