Question about solution in 6.8

#1

I have a question about the solution to 6.8 “Buy and Sell a Stock Twice”. I understand that the problem can be completed in O(n) time, but I don’t see why you need two traversals through the array. The way I solved it was to maintain an array of the highest profit seen so far at each i, the index of the minimum so far and the overall profit. My traversal, in ruby, looks like this:

(1...array.size).each do |i|
  current_profit = array[i] - min_value
  profits[i] = [current_profit, profits[i-1]].max
  previous_max = profits[min_index]
  overall_profit = [current_profit + previous_max, overall_profit].max
  if array[i] < array[min_index]
    min_index = i
  end
end

The general approach is to calculate the profit at each i and then add the best profit before the current min_index. Is there a case that breaks my solution?

0 Likes
#2

Hey Kavinder,

Thanks for your question, and it is an interesting idea for sure. It seems a good idea but I am not sure how the ruby code works very clearly. However, after examining the code, I don’t know how you update min_value. This introduces a concern that previous_max may use use the same min_value or min_value that is illegal—your algorithm may have something like buy, buy, sale, sale, which is illegal in our problem definition. The problem requires you to buy, sell, buy, sell; otherwise, you might just use the answer from “Buy and Sell Stock Once” times 2 as the answer of this problem (i.e., buy twice at the lowest point, and sell twice in the highest point).

Since your code is not complete, and another easy way to examine your idea is to write a simple O(n^2) checker to compare your program with that. If you don’t know how that works, you can download the code from our Github to see how we examine the solution by using this simple O(n^2) checker.

Please feel free to let me know what you think, and I am looking forward to your idea, which is interesting for sure!

0 Likes