Given an array, its ith element is the price of a given stock on the ith day. If you only allow one trade (buy and sell a stock once), design an algorithm to calculate the maximum profit you can make. Note: You cannot sell a stock before you buy it.

Source: LeetCode link: leetcode-cn.com/problems/be… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Violent solution: because can buy and sell only once, so can cycle in turn, find the optimal solution

Implementation code:

[7,1,5,3,6,4] ** * the best time to buy and sell stocks: only once@param prices
	 * @return* /
	public static int maxProfit_violence(int[] prices) {
		int maxProfit = 0;
		for (int i = 0; i < prices.length; i++) {
			for (int j = i+1; j < prices.length; j++) {
				if(prices[j] - prices[i] > maxProfit) { maxProfit = prices[j] - prices[i]; }}}return maxProfit;
    }
Copy the code

Dynamic programming solution:

S1: Record the minimum bought before today S2: calculate the maximum profit from selling today S3: compare the maximum profit from each dayCopy the code

Code:

* s1: Record the minimum value bought before today * s2: calculate the maximum profit from selling today * s3: compare the maximum profit from selling each day **@param prices
	 * @return* /
	public static int maxProfit_dynamic(int[] prices) {
		if (prices.length <= 1) {
			return 0;
		}
		int maxProfit = 0;
		int min = prices[0];
		for (int i = 0; i < prices.length; i++) {
			maxProfit = Math.max(maxProfit, prices[i] - min);
			min = Math.min(min, prices[i]);
		}
		return maxProfit;
    }
Copy the code