问题1比较简单, 使用一个pre变量,记录之前最小值就可以了
public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int max = 0; int minPre = prices[0]; for (int i = 1; i < prices.length; i++) { int price = prices[i]; if(price<minPre){ minPre = price; }else if(price-minPre>max){ max = price-minPre; } } return max; }
问题2细想,其实也比较简单,就是将所有递增的两个数的差加起来
public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int preMin = prices[0]; int sum = 0; for (int i = 1; i < prices.length; i++) { int price = prices[i]; if (price < preMin) { preMin = price; } else if (price > preMin) { sum += price - preMin; } preMin = prices[i]; } return sum; }
第三个问题,需要细想下,直观的想法,将数组一份为二,得到没有个子数组的最大值,这个算法是O(n2)的时间复杂度,不过;仔细思考,其实我们可以通过三次o(n)的遍历,得到所求。事先我们可以得到正向遍历,反向遍历,每个index上的最大利润值,最后一次遍历就可完成计算。
public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int[] maxLeft = new int[prices.length]; int preMin = prices[0]; for(int i=1; i<prices.length; i++){ int price = prices[i]; if(price<preMin){ preMin=price; maxLeft[i] =maxLeft[i-1]; }else if(price-preMin>maxLeft[i-1]) { maxLeft[i]=price - preMin; }else { maxLeft[i] =maxLeft[i-1]; } } int[] maxRight = new int[prices.length]; int preMax = prices[prices.length-1]; for(int i=prices.length-2; i>=0; i--){ int price = prices[i]; if(price>preMax){ preMax = price; maxRight[i] = maxRight[i+1]; }else if(preMax - price>maxRight[i+1]){ maxRight[i]=preMax - price; }else { maxRight[i] = maxRight[i+1]; } } int max =0; for(int i=1; i<prices.length; i++){ if(maxLeft[i]+maxRight[i]>max){ max = maxLeft[i]+maxRight[i]; } } return max; }
相关推荐
leetcode题目:Best Time to Buy and Sell Stock II
leetcode-java leetcode刷题笔记 已做题目列表 1.Two Sum 3.Longest Substring Without Repeating Characters 5.Longest Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted Array 53....
leetcode LeetCode 解决题目的总数: 136/1753 微信公众号: 工程师Ruojhen 算法-动态规划 题号 名称 English Name 题解 53 最大子序和 Maximum Subarray 70 爬楼梯 Climbing Stairs 121 买卖股票的最佳时机 Best Time...
股票收益leetcode LeetCode 股票问题 Best Time to Buy and Sell Stock (Easy) 一次交易,找最大收益 for i in prices: low = min(low, i) profit = max(profit, i-low) Best Time to Buy and Sell Stock II (Easy) ...
[Bitwise AND of Numbers Range](https://leetcode.com/problems/bitwise-and-of-numbers-range/) | [C++](./C++/bitwise-and-of-numbers-range.cpp) [Python](./Python/bitwise-and-of-numbers-range.py) | _O(1)_...
股票买卖最佳时机leetcode 该存储库包含买卖股票的最佳时间的所有变体。 所有这些练习题都可以在 leetcode 上找到。
LeetCode题解 - Java语言实现-181页.pdf
股票买卖最佳时机leetcode 金融科技:用交易费买卖股票的最佳时机 使用动态编程(Python 实现)找到以交易费买卖股票的最佳时间。 算法 使用动态规划沿着给定的价格向量计算最佳动作序列。 DP 在每个时间 t 记录以下...
leetcode leetcode The optimum C++ solutions for the leetcode 这是我自己写的leetcode的题解,目前已经完成了70%左右,后续部分会很快更新 这里放上来的代码都能保证是最优解(复杂度最优) 当然有些题目因为测试...
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...
股票买卖最佳时机leetcode 金融科技:用交易费买卖股票的最佳时机 使用动态编程(Python 实现)找到以交易费买卖股票的最佳时间。 算法 使用动态规划沿着给定的价格向量计算最佳动作序列。 DP 在每个时间 t 记录以下...
股票买卖最佳时机leetcode 买卖股票的最佳时机 Java 程序选择在给定的股票价格数组中买卖股票的最佳时间。
力扣解题java版本
股票买卖最佳时机leetcode GitFitCode 配对编码挑战! 买卖股票的最佳时机 让我们弄清楚什么时候买一些股票! 这不应该在现实生活中使用。 现在不管你认为你的算法有多好:)。 我确实鼓励您选择一只您感兴趣的股票,...
股票买卖最佳时机leetcode 买卖股票的最佳时机-2 假设您有一个数组,其中第 i 个元素是给定股票在第 i 天的价格。 设计一个算法来找到最大的利润。 您可以根据需要完成任意数量的交易(即多次买入和卖出一股股票)。...
Best Time to Buy and Sell Stock III Best Time to Buy and Sell Stock IV Best Time to Buy and Sell Stock with Cooldown Interleaving String Scramble String Minimum Path Sum Edit Distance Decode Ways ...
LeetCode 400题目 Java版本 (LeetCode is the platform to help you enhance your skills, expand your knowledge and prepare for technical interviews.)
公众号 coding 笔记、点滴记录,以后的文章也会...最近花时间分门别类整理了 LeetCode 的前 500 题,把相似的题目都放在了一起,比如Best Time to Buy and Sell Stock的6道题,这些题目放在一起刷效果更好。 简书博客:
Algorithm-awesome-java-leetcode.zip,Java解决方案(更新)的LeetCode算法。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-java, 我的LeetCode在线在线判断解决方案 leetcode-java我的 LeetCode在线判断系统的解决方案。插件生成状态 要求Java> = 1.6Gradle> = 1.8.6 ( 1.8.6 是我唯一尝试的版本)生成 Eclipse 项目