My o(n) solution


  • 1
    L
    1. Calculate the difference of price between yesterday and today. For example , given an array A={6,1,3,4}, We can get a new array B={0,-5,2,1}, which record the difference of price between yesterday and today.

    2. Calculate maximum sum of Consecutive sub-array of B , in this example ,its result is 2+1=3. So 3 is the maximum profit.
      following is my code:

      int maxsub(vector<int> &diff)
      {
      	int maxNum=INT_MIN;
      	int curSum=INT_MIN;
      	int len=diff.size();
      	if(len==0)	return 0;
      	for(int i=0;i<len;i++)
      	{
      		if(curSum<0)
      		{
      			curSum=diff[i];
      			if(curSum>maxNum)
      				maxNum=curSum;
      		}
      		else
      		{
      			curSum += diff[i];
      			if(curSum>maxNum)
      				maxNum=curSum;
      		}
      	}
      	return maxNum;
      }
       int maxProfit(vector<int> &prices) {
      	int len=prices.size();
      	if(len==0)	return 0;
      	vector<int> diff(len);
      	diff[0]=0;
      	for(int i=1;i<len;i++)
      		diff[i]=prices[i]-prices[i-1];
      	return maxsub(diff);
       }

Log in to reply
 

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