买卖股票的最好时机-贪心算法-java实现

描述

假设你有一个数组，其中第i 个元素是股票在第 i 天的价格。
你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。

示例1

输入：[1,4,2]
返回值：3

示例2

输入：[2,4,1]
返回值：2

下面说一下思路，其实这道题是想将找出值a与值b之间的差值最大的值，且值a一定要在值b前面，那么我们其实就可以边遍历边算当前的最大差值是多少，直到最末，这种也是四大算法中的贪婪算法思想的体现，算出当前认为最大的值，随着遍历直到有更大的值出现，才换掉。具体实现逻辑如下：

package easy;
/*** 买卖股票的最好时机* 假设你有一个数组，其中第\ i i 个元素是股票在第\ i i 天的价格。* 你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。* 输入：* [1,4,2]* 返回值：* 3* 输入：* [2,4,1]* 返回值：* 2*/
public class MaxProfit {/**** @param prices int整型一维数组* @return int整型*/public int maxProfit (int[] prices) {//r如果输入数组为[]或者[6,5,4,3,2,1]或者[3]返回0,其他的情况正常返回if(prices.length<2){return 0;}//算法思路//1、假设第一个数字是最小的，最大收益为0//2、开始遍历，如果当前值大于最小的，则减去最小的值为最大收益，与当前最大收益进行比较，若//比它大则交换，小则不作操作，下一次//如果当前值小于目前最小的，那交换数字，下一次int min=prices[0];int maxprice=0;for(int i=0;i<prices.length;i++){if(prices[i]>min){int curMaxprice=prices[i]-min;if(curMaxprice>maxprice){maxprice=curMaxprice;}}else{min=prices[i];}}return maxprice;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！