121.买卖股票的最佳时机

/*
 * @lc app=leetcode.cn id=121 lang=typescript
 *
 * [121] 买卖股票的最佳时机
 */

// @lc code=start

// 数据量过大时，性能很差
// function maxProfit(prices: number[]): number {
// 	let maxs: number[] = [];
// 	prices.map((price, index) => {
// 		if (index !== prices.length - 1) {
// 			let arr = prices.slice(index, prices.length);
// 			let count: number[] = [];
// 			arr.map(cl => {
// 				count.push(cl - price);
// 			});
// 			maxs.push(Math.max(...count));
// 		}
// 	});

// 	let maxData = Math.max(...maxs);
// 	if (maxData <= 0) {
// 		return 0;
// 	} else {
// 		return maxData;
// 	}
// }

// function maxProfit(prices: number[]): number {
// 	let min = prices[0];
// 	let res = 0;
// 	prices.map(el => {
// 		if (el < min) {
// 			min = el;
// 		} else if (el - min > res) {
// 			res = el - min;
// 		}
// 	});
// 	return res;
// }

// function maxProfit(prices: number[]): number {
// 	let min = prices[0];
// 	let dp = Array.from({ length: prices.length }, () => 0);
// 	dp[0] = 0;
// 	for (let i = 1; i < prices.length; i++) {
// 		if (min > prices[i]) {
// 			min = prices[i];
// 		}
// 		dp[i] = Math.max(dp[i - 1], prices[i] - min);
// 	}
// 	return dp[dp.length - 1];
// }

function maxProfit(prices: number[]): number {
	let min = prices[0];
	let res = 0;
	for (let i = 1; i < prices.length; i++) {
		if (min > prices[i]) {
			min = prices[i];
		}
		res = Math.max(res, prices[i] - min);
	}
	return res;
}

console.log(maxProfit([7, 6, 4, 3, 1]));

// @lc code=end