给出一个包含N个元素的数组,数组中的每个元素代表每一天的股票的买卖价格。现在给你个任务是在任意的时刻先买股票,之后卖出股票。要求是使得买卖股票的利益最大化,算法的时间和空间复杂度尽可能达到最优。
看到本题,绝大多数人的第一思路大概都能想到用最大值去减最小值。但是问题出来了,最小值出现的位置不一定在最大值出现的位置前面,这样就违背了先买后卖的现实规律。
对于这个问题,为了保证最小值出现在当前最高价格之前。正确的思想应该是假设任意时刻都是可以卖的时间点,在这之前的最低价买入,扫描整个数组之后,整体的最大利益就能够计算出来!
public class Demo {
public static void main(String[] args) {
int[] nums = {
4, 5, 6, 9, 26, 39, 1,
18, 24, 21, 19, 33};
int min = nums[0];
int maxProfit = 0;
for (int num : nums) {
if (num < min) {
min = num;
}
if (num - min > maxProfit) {
maxProfit = num - min;
}
}
System.out.println(
"Max profit is: " + maxProfit);
}
}