首页 > 代码库 > [LeetCode]121 Best Time to Buy and Sell Stock
[LeetCode]121 Best Time to Buy and Sell Stock
https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/
http://blog.csdn.net/linhuanmars/article/details/23162793
public class Solution { public int maxProfit(int[] prices) { // Solution A: return maxProfit_DP(prices); // Solution B: // return maxProfit_Binary(prices); } ///////////////////////////// // Solution A: DP // // global: 全局最优 // local: 在今天卖出的最优 // 在i-1 天卖出 的是 local // 在i天卖出的是 max(local + (price[i] - price[i - 1]), 0) private int maxProfit_DP(int[] prices) { if (prices == null || prices.length <= 1) return 0; int local = 0; int global = 0; for (int i = 1 ; i < prices.length ; i ++) { local = Math.max(local + prices[i] - prices[i - 1] , 0); global = Math.max(local, global); } return global; } ///////////////////////////// // Solution A: Binary // public int maxProfit_Binary(int[] prices) { if (prices == null || prices.length == 0) return 0; // Invalid input. Values value = calc(prices, 0, prices.length - 1); return value.pro; } private Values calc(int[] prices, int low, int high) { if (low == high) { return new Values(prices[low], prices[low], 0); } int mid = (low + high) / 2; Values left = calc(prices, low, mid); Values right = calc(prices, mid + 1, high); int max = Math.max(left.max, right.max); int min = Math.min(left.min, right.min); int pro = Math.max(left.pro, right.pro); pro = Math.max(pro, right.max - left.min); return new Values(max, min, pro); } private static class Values { Values(int max, int min, int pro) { this.max = max; this.min = min; this.pro = pro; } int max; int min; int pro; } }
[LeetCode]121 Best Time to Buy and Sell Stock
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。