Best Time to Buy and Sell Stock

Say you have an array for which the i-th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Solution: 
cannot use max - min since we have to buy the stock before sell...
cannot find min first then find the max after min, since the maximum gap might be another one, for example, min might be the last element
exhaustive search costs O(n^2) 
divide and conquer: find the min of the first half and the max of the last half. compare the gap, and the gaps in each half.
T(n) = 2T(n/2) + O(n) = O(nlogn)
The following code passes LeetCode online large judge 
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int s = prices.size();
        if(s < 2) return 0;
        if(s == 2) return max(prices[1]-prices[0], 0);
        vector<int> left_prices;
        vector<int> right_prices;
        int min = prices[0];
        int max = prices[floor((s-1)/2)+1];
        for(int i = 0; i < s; i++) {
            if(i <= floor((s-1)/2)) {
                left_prices.push_back(prices[i]);
                if(min > prices[i]) min = prices[i];
            }
            else {
                right_prices.push_back(prices[i]);
                if(max < prices[i]) max = prices[i];
            }
        }
        int left = maxProfit(left_prices);
        int right = maxProfit(right_prices);
        int gap = max - min;
        if(gap >= left && gap >= right)
            return gap;
        else if(left >= gap && left >= right)
            return left;
        else
            return right;
    }
};

Update: linear algorithm for this problem 

 Traversing the entire array, keeping tracking the current min value, and upgrading the current max gap

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int min = 0;
        int gap = 0;
        for(int i = 0; i < prices.size(); i++) {
            if(prices[i] < prices[min]) min = i;
            if(prices[i] - prices[min] > gap) gap = prices[i] - prices[min];
        }
        return gap;
    }
};

Comments

Post a Comment

Popular posts from this blog

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.  Try to solve it in linear time/space.  Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range. In order to solve this in linear time, we cannot use general sorting algorithm. Here we use bucket sort. First, we scan the array to find the min and the max values.   We can then create n - 1 buckets with equal size. Suppose we have n elements in total, then we have n - 2 elements except the min and the max. Scan the array again to put the n - 2 elements into these buckets. We should have at least one empty bucket. For each bucket, we record the min and the max for all the elements within that bucket.  Finally, we scan all the buckets, and maintain the maximum gap. Note that the maximum gap between the successive elements in the sorted array can only be the gap between
Read more

[ITint5] Maximum Subarray for a Circular Array

http://www.itint5.com/oj/#8 Classic DP problem, which has also appeared in Leetcode as Maximum subarray . The only difference is, in this problem, empty subarray (where sum is 0) is allowed. So instead of return ret, we could simply return max(0, ret). http://www.itint5.com/oj/#9 Calculate the maximum subarray for a circular array. For example, [1, 3, -2, 6, -1], we should return 9 since 6 + (-1) + 1 + 3 = 9. The following solution might not be optimized. Suppose that the maximum subarray is from A[i] to A[j]. The idea is, consider the following different scenarios: i <= j: it is the same as classic problem. i > j: the sum is A[i : end] + A[start : j]. So we can use two additional arrays: left[j] = maximum subarray, starts from A[start] and ends no later than A[j] right[i] = maximum subarray, starts no earlier than A[i] and ends at A[end] The following code passes the online judge. However, we need O(4n) in time and O(2n) in space. Not sure how to improve this.
Read more

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.   The path may start and end at any node in the tree. Solution: For root node, first check two subtrees and figure out the path with maximum sum in each subtree (and the path must contains the root node). More precisely, we can compare root->val, root->val + leftsubtree, root->val + rightsubtree. But this is not enough since the maximum path might contains two subtrees. We have to compute the value of root->val + leftsubtree + rightsubtree as well. The problem is, we cannot directly return this value since this path cannot go to upper nodes anymore. So we also use another global variable to store the maximum sum in each recursion, and update this variable once we find any path with larger sum. The following code passes the LeetCode Online Large Judge. Thanks for the useful comments.
Read more