#include "pch.h"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <time.h>

using namespace std;

int get_max_profit(vector<int> prices);

int main()
{
	vector<int> prices(10);

	prices = { 25, 7, 5, 8, 11, 9 };
	int m_profit = get_max_profit(prices);
	//returns 6 (buying for 5 and selling for 11)
	cout << "1st:the max profit should be 6: " << m_profit << endl;

	prices = { 10, 7, 11, 5, 8, 9 };
	m_profit = get_max_profit(prices);
	//returns 4 (buying for 7 and selling for 11, or buying for 5 and selling for 9)
	cout << "2nd:the max profit should be 4: " << m_profit << endl;

	prices = { 10, 7, 11, 5, 8, 7 };
	m_profit = get_max_profit(prices);
	//returns 6 (buying for 7 and selling for 11)
	cout << "3rd:the max profit should be 4: " << m_profit << endl;

	prices = { 10, 7, 9, 5, 8, 7 };
	m_profit = get_max_profit(prices);
	//returns 6 (buying for 5 and selling for 8)
	cout << "4th:the max profit should be 3: " << m_profit << endl;

	prices = { 10, 7, 9, 5, 8, 7 };
	m_profit = get_max_profit(prices);
	//returns 6 (buying for 5 and selling for 8)
	cout << "5th:the max profit should be 3: " << m_profit << endl;

	prices = { 16, 9, 7, 5, 3, 10 };
	m_profit = get_max_profit(prices);
	//returns 6 (buying for 3 and selling for 10)
	cout << "6th:the max profit should be 7: " << m_profit << endl;

	//To test performance
	srand(unsigned(time(NULL)));
	prices.resize(10000000);
	generate(prices.begin(), prices.end(), rand);
	clock_t t_start = clock();
	m_profit = get_max_profit(prices);
	clock_t t_end = clock();
	cout << "Final:the max profit from a random array with 10,000,000 numbers: " << m_profit << endl;
	cout << "Time used: " << ((t_end - t_start) / CLOCKS_PER_SEC) << " seconds" << endl;
}

//this is to get the max gap in an array supposing gap can only be a later number minus a former number
int get_max_profit(vector<int> prices) {
	int currMax = 0;
	int totalMax = 0;

	int count_prices = prices.size();
	if (count_prices <= 1) {
		return 0;
	}

	for (int i = 1; i < count_prices; i++) {
		currMax = max(0, currMax + prices[i] - prices[i - 1]);
		totalMax = max(totalMax, currMax);
	}
	return totalMax;
}