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

Answer 1

We can also solve this with an array, a stack and binary search in O(n log n) time and O(n) space. Iterate backwards and at each iteration, if the value is higher than the last element in the array, add (value, index, 0, 0) ((value, index, count, cost)) to the array record; otherwise, find the first higher element (with binary search), add to its count and cost, and prepend the index to the stack of contributors.

0  1  2  3   4  5
70 40 90 110 80 100

i:5
  [(100, 5, 0)]
  contributors: []
i:4
  80 < 100
  [(100, 5, 1, 80)]
  contributors: [4]
i:3
  110 > 100
  [(100, 5, 1, 80), (110, 3, 0, 0)]
  contributors: [4]
i:2
  90 < 100
  [(100, 5, 2, 170), (110, 3, 0, 0)]
  contributors: [2, 4]
i:1
  40 < 100
  [(100, 5, 3, 210), (110, 3, 0, 0)]
  contributors: [1, 2, 4]
i:0
  70 < 100
  [(100, 5, 4, 280), (110, 3, 0, 0)]
  contributors: [0, 1, 2, 4]

Now iterate over our new, monotonically increasing, record. At each iteration on the record, add the count and cost from the previous tuple, then "pop" counts and cost for each element in the contributor stack while its index is greater than the current one in the record:

0  1  2  3   4  5
70 40 90 110 80 100

[(100, 5, 4, 280), (110, 3, 0, 0)]

i:0
  best = 4 * 100 - 280 = 120

i:1
  add count and cost:
  (110, 3, 0 + 4, 0 + 280)

  pop count and cost for each
  contributor with a greater index:
  contributors: [0, 1, 2, 4]
  index 4 > 3
  (110, 3, 4 - 1, 280 - 80)
    profit = 3 * 110 - 200 = 130
    best = 130
    contributors: [0, 1, 2]

Answer 2

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).