首页 > 代码库 > LeetCode--Best Time to Buy and Sell Stock (贪心策略 or 动态规划)
LeetCode--Best Time to Buy and Sell Stock (贪心策略 or 动态规划)
Best Time to Buy and Sell Stock
Total Accepted: 14044 Total Submissions: 45572My Submissions
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock),
design an algorithm to find the maximum profit.
解题思路:
贪心法:
分别找到价格最低和最高的一天,低进高出,注意最低的一天要在最高的一天之前。
把原始价格序列变成差分序列,也就是对于元素j,在该点卖出的价格等于prices[j] 减去它前面元素中最小的值。这样遍历一遍数组就OK了。
本题也可以做是最大m 子段和,m = 1 。
动态规划法:
首先用prices[i] - prices[i-1] 将数组转化为 差分序列,那么问题就转化为在这个差分序列中找出一个最大( maximum )的连续的子序列和的问题,可以用http://blog.csdn.net/acema/article/details/26979779 类似方法求解。
备注:若采用暴利破解法,时间复杂度是O(n^2),会超出时间限制。
程序源代码:
贪心算法Java代码
public int maxProfit(int[] prices) { if(prices.length ==0) return 0; int i=0; int profit=0; int begMin= prices[0]; for(i=1; i<prices.length; ++i){ profit=Math.max(profit, prices[i]-begMin); begMin=Math.min(begMin, prices[i]); } return profit; }
动态规划:java代码
public int maxProfit(int[] prices) { int profit=0; int temp=0; for(int i=1; i<prices.length; ++i){ int diff=prices[i] - prices[i-1]; temp=Math.max(temp+diff, diff); profit=Math.max(profit, temp); } return profit; }
/** * 暴利枚举法,超出时间限制 * @param prices * @return */ public static int maxProfit2(int[] prices) { int profit= 0; for( int i=0; i<prices.length-1; ++i){ for (int j=i+1; j<prices.length; ++j){ profit = Math.max(prices[j]-prices[i], profit); } } return profit; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。