fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <limits>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. int main() {
  8. 	vector<int> prices{10, 4, 6, 8, 2, 5, 3, 9, 1};
  9. 	// sell at time [i] requires buy at minimum in range [0,i-1]
  10. 	// create vector of index at minimum for each range
  11. 	int currentMinimumIndex = 0;
  12. 	vector<int> minimums{0};
  13. 	for(size_t i = 1; i < prices.size(); ++i)
  14. 	{
  15. 		if (prices[i] < prices[currentMinimumIndex])
  16. 		{
  17. 			minimums.emplace_back(i);
  18. 			currentMinimumIndex = i;
  19. 		}
  20. 		else
  21. 			minimums.emplace_back(currentMinimumIndex);
  22. 	} // O(n)
  23.  
  24. 	// at this point we have a lookup table for minimum in every range
  25.  
  26. 	// attempt to maximize amount we can get if we sell at time i buy buying at minimum for (0,i-1)
  27. 	vector<int> maxSales{std::numeric_limits<int>::min()};
  28. 	for(size_t i=1;i<prices.size();++i)
  29. 	{
  30. 		maxSales.emplace_back(prices[i] - prices[minimums[i]]);
  31. 	} // O(n)
  32.  
  33. 	// find maximum element
  34. 	auto maxSum = std::max_element(std::begin(maxSales), std::end(maxSales)); // O(n)
  35. 	auto sellAt = std::distance(std::begin(maxSales), maxSum);
  36. 	auto buyAt = minimums[sellAt];
  37. 	std::cout << "Maximum profit is " << *maxSum << std::endl;
  38. 	std::cout << "If we buy at index " << buyAt << " (price: " << prices[buyAt] << ")"
  39. 	<< " and sell at " << sellAt << " (price: " << prices[sellAt] << ")" << std::endl;
  40.  
  41. 	return 0;
  42. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Maximum profit is 7
If we buy at index 4 (price: 2) and sell at 7 (price: 9)
https://ideone.com/sUHro8
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!