Interview problem : Buy and sell stocks to maximize profit with constraint of not buying once you sell

Question

There are a classical interview problem of maximizing profit, buying stocks with one transaction, n transactions and k transactions allowed.

I was asked a similar problem but with a twist constraint: You may buy a stock any number of times(no more than one unit on any day), but you cannot buy after you've sold the stock.

This has a lemma that you sell only once.

eg: 70 40 90 110 80 100

Option 1 : B B B Sell _ _ = 130

Option 2 : B B B X B Sell = 120

Older problems

https://www.geeksforgeeks.org/stock-buy-sell/

https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-twice/

https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/

https://www.geeksforgeeks.org/maximum-profit-after-buying-and-selling-the-stocks-any-number-of-times/

Stackoverflow discussions

maximizing profit for given stock data via DP

Maximizing profit for given stock quotes

Maximum profit by buying and selling a share exactly k times

Best time to Buy and Sell stock modified version

I'm confused by the multiple buying. Is there a limit to the amount you can buy on a given day? Your posted examples imply a 1-unit limit. — Prune
@Prune, I think the only reasonable interpretation of the examples is that you can buy 1 or 0 each day and sell all on some other day and that's all you can do. — SergGr
@SergGr: Now that I've read it four times, I think I've resolved the semantic problems. You're right. — Prune

Paul Paul · Accepted Answer · 2019-01-11T21:34:12

This can be solved in O(n lg n) with O(n) space using a BST.

The datastructure

class BSTNode{
    BSTNode(val){
        this.val = val
        this.sum = sum
        this.left = this.right = null
        this.count = 1
    }

    insert(val){
        if(val < this.val)
            insert val into the left subtree
        else if(val > this.val)
            insert val into the right subtree

        this.sum += val
        this.count++
    }

    count_sum_nodes_upper_bound(val){
        if(val < this.val)
            return this.left.sum_nodes_lower_bound(val)
        else if(val == this.val)
            return this.left.sum, this.left.count
        else{
            right_sum, right_count = this.right.sum_nodes_lower_bound(val)

            return (this.sum - this.right.sum + right_sum),
                   (this.count - this.right.count + right_count)
        }
    }
}

The above is just a rough outline of what the proper BST should look like. In practice you'd probably want to use a balanced tree instead and check whether subtrees are present in count_sum_nodes_lower_bound. The above code explained:

Each BSTNode holds in addition to the standard-attributes of a BST the properties sum and count, where count is the number of elements in the subtree and sum is the sum of all elements in it.

Insert works in the same way in which it would work in a normal BST, except that in each node the corresponding sum and count need to be updated. If the same value is inserted more than once, sum and count will be updated to reflect the duplicity.

The central piece however is the method count_sum_nodes_upper_bound, which computes the count of elements and their sum for a given upper bound. For a given upper-bound b three cases can occur on a node with value v:

b < v: all elements that are relevant are contained in the left-subtree
b == v: the left subtree is the result of the query
b > v: all values in the left subtree and the current node are part of the subset. In addition some nodes of the right subtree are also part of the result, which we need to find by recursion.

The search

With this BST we can now easily find the solution to the above problem:

maximize_profit(A){
    node = BSTNode(A[0])
    max = 0
    max_idx = -1

    for(i in 1..(A.length - 1)){
        sum, count = node.count_sum_nodes_upper_bound(A[i])
        gain = A[i] * count - sum 

        if(max < gain){
            max = gain
            max_idx = i
        }

        node.insert(A[i])
    }

    return max_idx
}

The above code finds the index of the optimal selling-date based on the values stored in the BST. At the start of iteration i, node will contain all values in A[0..i - 1]. The only stocks that make sense to buy are the ones with a value lower than A[i]. We can query the number and sum of these stocks in O(lg n) using count_sum_nodes_upper_bound. The total gain from these stocks if their sum is s and their count c is then the amount at which all stocks are sold (A[i] * c) subtracted by the value at which each stock was bought (s).

Getting the stocks to buy can afterwards trivially be done in O(n) by filtering A (or by expanding the functionality of the BST according to your needs).

Interview problem : Buy and sell stocks to maximize profit with constraint of not buying once you sell

2 Answers

The datastructure

The search