问题
给定一个数组,数组中每个元素代表当前股票在这一天的价格
prices = {7,1,5,3,6,4}
第一天价格:7
第二天价格:1
第三天价格:5
prices[index][price]
计算在固定天数内能获取到的最大利润为多少,不能同时进行多笔交易,购买之前必须将手上的股票卖掉。
关键字
贪心算法
不从整体最优考虑,只关注局部最优,做出当前最优解。
思路
两两比较,获取当前的差值,并不断进行累加。
假定存在数组{a,b,c,d,e},则 total=(b-a) + (c-b) + (d-c) + (e-d);
image.png
实现
public class MaxProfit {
public static void main(String[] args) {
//初始数组
int[] nums = new int[]{7,1,5,3,6,4};
int total = maxProfit(nums);
System.out.println(total);
}
private static int maxProfit(int[] nums) {
//初始利润
int total = 0;
//遍历数组,两两获取差值,并累加
for (int i=0;i<nums.length-1;i++){
total+=Math.max(nums[i+1]-nums[i],0);
}
return total;
}
}
网友评论