O(n) time C++ solution with good explanation


  • 3

    My submitted code:

    class Solution {
        public:
            int maxProfit(vector<int>& prices) {
                if( prices.size() == 0 ) return 0;
                vector<int> left(prices.size() + 1);
                int cur = 0, last = 0, maxSum = 0, right = 0, tmp;
                for( int i=1; i<prices.size() + 1; i++ ) {
                    if( last < 0 ) cur = (i == 1 ? 0 : (prices[i-1] - prices[i-2]));
                    else cur = (i == 1 ? 0 : (prices[i-1] - prices[i-2])) + cur;
                    last = cur;
                    left[i] = cur > left[i-1] ? cur : left[i-1];
                }
                last = 0;
                cur = 0;
                for( int i=prices.size()-1; i>=0; i-- ) {
                    if( last < 0 ) cur = ( i == 0 ? 0 : prices[i] - prices[i-1] );
                    else cur = ( i == 0 ? 0 : prices[i] - prices[i-1] ) + cur;
                    last = cur;
                    tmp = right;
                    right = cur > tmp ? cur : tmp;
                    if( left[i] + right > maxSum ) maxSum = left[i] + right;
                }
                return max(maxSum, left[prices.size()]);
            }
    };
    

    The problem can be converted to another problem.

    For example, if the prices list is [6,1,3,2,4,7], if we look at the difference of current price with previous price, the difference array will look like this: [0, -5, 2, -1, 2, 3 ], let's call it diff list. Now if you can only make one transaction to get the maximum profit, you just need to find a continuous sub array that the sum of it is maximum. In this case, the sub array would be [2, -1, 2, 3], sum it up you have 6. If you are allowed to do at most two transactions, you can find two arrays, [2], [2,3], sum them up you have 7, happen to be the maximum profit you can possibly get.

    Now let's focus on this problem, how to find two sub arrays in the difference array so that their sum is maximum?

    We can prepare two arrays, left[size+1] and right[size+1], left[i] means the maximum sum of a sub array you can get from diff[0 ... i-1], right[i] means the maximum sum of a sub array you can get from right[ i+1....size], then we compare all left[i] + right[i], and left[size](If we choose to make only one transaction), that would be the maximum profit we can have.

    So, we have unoptimised code like this:

    class Solution {
        public:
            int maxProfit(vector<int>& prices) {
                if( prices.size() == 0 ) return 0;
                vector<int> diff(prices.size());
                vector<int> left(prices.size() + 1), right(prices.size() + 1);
                for( int i=1; i<prices.size(); i++ ) diff[i] = prices[i] - prices[i-1];
                int cur = 0, last = 0, maxSum = 0;
                for( int i=1; i<prices.size() + 1; i++ ) {
                    if( last < 0 ) cur = (i == 1 ? 0 : diff[i-1]);
                    else cur = (i == 1 ? 0 : diff[i-1]) + cur;
                    last = cur;
                    left[i] = cur > left[i-1] ? cur : left[i-1];
                }
                right[prices.size()] = 0;
                last = 0;
                cur = 0;
                for( int i=prices.size()-1; i>=0; i-- ) {
                    if( last < 0 ) cur = ( i == 0 ? 0 : diff[i]);
                    else cur = ( i == 0 ? 0 : diff[i]) + cur;
                    last = cur;
                    right[i] = cur > right[i+1] ? cur : right[i+1];
                    if( left[i] + right[i] > maxSum ) maxSum = left[i] + right[i];
                }
                return max(maxSum, left[prices.size()]);
            }
    };
    

    Obviously we can calculate the difference on the fly, and right list is not necessary. With a little optimisation, it will look like my submitted code above.


  • 0
    Y

    your example is wrong.[0, -5, 2, -1, 2, 3 ] clearly you can get as high as 8, not 6 as you wrote.


Log in to reply
 

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