Best Time to Buy and Sell Stock

Say you have an array for which the i^th element isthe price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buyone and sell one share of the stock), design an algorithm to find the maximumprofit.

HideTags

Array Dynamic Programming

#pragma once
#include
#include
using namespace std;

/*i+1 減去i ，構造每天盈利數組，求子數組最大和*/

//求子數組最大和，若和為負，應返回0
int findMax(int *list, int n)
{
	int maxsum = 0;//初始設為0，可保證最後返回大於等於0
	int sum = 0;
	for (int i = 0; i < n;i++)
	{
		sum += list[i];
		if (sum > maxsum)
			maxsum = sum;
		else
			if (sum <= 0)
				sum = 0;
	}
	return maxsum;
}

int maxProfit(vector &prices) 
{
	if (prices.size() == 0)
		return 0;
	int *list = new int[prices.size() - 1];
	for (int i = 0; i < prices.size() - 1; i++)
		list[i] = prices[i + 1] - prices[i];
	return findMax(list, prices.size() - 1);
}

void main()
{
	
	system("pause");
}