best time to buy and sell stockI&II&III

best time to buy and sell stockI&II&III

I

Only can buy and sell one time. Go through the vector, update the minnum value and result.Time complexity O(n), space complexity O(1).

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int> &prices) {
 4         int n = prices.size();
 5         if ( n <= 1 ) {
 6             return 0;
 7         }
 8         int now = prices[0];
 9         int result = 0;
10         for ( int i = 1; i < n; i++ ) {
11             if ( prices[i] >= now ) {
12                 result = max(result,prices[i]-now);
13             } else {
14                 now = prices[i];
15             }
16         }
17         return result;
18     }
19 };

II

This description is really terrible. After looking around I finally know the meaning. You must sell the stock before you buy. You can both sell and buy in the same day. It seemes easier then I. If the price is higher than yeseterday, sell and buy a new one. Otherwise, we do not buy yesterday. class Solution { public: int maxProfit(vector &prices) { int n = prices.size(); if ( n < 2 ) { return 0; } int result = 0; int now = prices[0]; for ( int i = 1; i < n; i++ ) { if ( now < prices[i] ) { result += prices[i]-now; } now = prices[i]; } return result; } };

III

After look around, I know this meaning. We can buy two times and sell two time, but in our hand there should be only one stack. This problem seems harder than both two before. Simplify this problem into two problems. Because we can only hold one stack, it means we need find a day. Before that day we need finish buy and sell once or zero, and after that day we need finish buy and sell once or zero. Sum the max profit before that day and after that day, and find the max value day.

  • First problem, find the max profit(one transaction) before each day.
  • Second problem, find the max profit(one transaction) after each day.
  • Third problem find the maxprofit day.
 1 class Solution {
 2 public:
 3     int maxProfit(vector<int> &prices) {
 4         int n = prices.size();
 5         if ( n < 2 ) {
 6             return 0;
 7         }
 8         int result = 0;
 9         int left[n];
10         int right[n];
11         left[0] = 0;
12         int now = prices[0];
13         for ( int i = 1; i < n; i++ ) {
14             if ( prices[i] > now ) {
15                 left[i] = max(prices[i] - now,left[i-1]);
16             } else {
17                 left[i] = left[i-1];
18                 now = prices[i];
19             }
20         }
21         right[n-1] = 0;
22         now = prices[n-1];
23         for ( int i = n-2; i >= 0; i-- ) {
24             if ( prices[i] < now ) {
25                 right[i] = max(now-prices[i],right[i+1]);
26             } else {
27                 right[i] = right[i+1];
28                 now = prices[i];
29             }
30         }
31         for ( int i = 0; i < n; i++ ) {
32             result = max(result,left[i]+right[i]);
33         }
34         return result;
35     }
36 };

Loading Disqus comments...
Table of Contents