过年偷懒了两周现在又该好好学习了。今天白天浪费了太多时间于是今晚选择刷两道又是之前算法课水过的题。看着当年的记录居然觉得也许或许当时可能是自己想出来的然而今天还是没想到做法QAQ题目Say you have an array for which theith element is the price of a given stock on dayi.If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.Note that you cannot sell a stock before you buy one.Example 1:Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price 1) and sell on day 5 (price 6), profit 6-1 5. Not 7-1 6, as selling price needs to be larger than buying price.Example 2:Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit 0.题目的要求即是给出一个数组找出两数之差的最大值其中较大值在较小值后面。这道题一看上去就觉得应该是动态规划来解可是想了一下觉得好像划分不出来子问题最后还是作弊看了以前的博客才醒悟——遍历整个数组记录当前的最大profit和最小的pricequote以前写的要先找出当前最小值并在循环的时候将现价与当前最小值相减得到的数字与当前最大利润进行比较。醒悟以后很快写好了代码又想了一下觉得不太像动态规划看了discussion里面的解答才恍然大悟嗯其实就是自己懒得去仔细推敲了这种偷懒的毛病要改其实这个的子问题相当于max(profit[i - 1], prices[i] - min_price)只是由于只有第一个元素需要存储因此这个问题就简化得不太像动态规划了。代码如下运行时间8ms100%空间9.6M100%class Solution { public: int maxProfit(vectorint prices) { if (prices.size() 0) { return 0; } int min_price prices[0]; int max_profit 0; for (int i 1; i prices.size(); i) { if (prices[i] min_price) { min_price prices[i]; } if (prices[i] - min_price max_profit) { max_profit prices[i] - min_price; } } return max_profit; } };然后呢在翻discussion的时候突然看到有人提出来Max Subarray的Kadane算法感觉这个名字有点熟悉啊一看居然是春节前刷过的题然而现在已经忘得一干二净了……这个帖子提出来说我们目前是给定了每天的股票价格而如果给出的是每天与前一天的差价那么我们要怎么做呢懒惰的我当然是懒得想啦继续看下去就发现居然这就变成了之前的Max Subarray那道题LeetCode 53. Maximum Subarray只需要找出连续的差价的最大值就是本题的答案了这种联系真是妙极了2022.10.24 Java嗯多少年过去了还是想不到思路。知道思路以后代码就好写了然而还是忘了length 0的情况。class Solution { public int maxProfit(int[] prices) { if (prices.length 0) { return 0; } int minPrice prices[0]; int maxProfit 0; for (int i 1; i prices.length; i) { if (minPrice prices[i]) { minPrice prices[i]; } if (maxProfit (prices[i] - minPrice)) { maxProfit prices[i] - minPrice; } } return maxProfit; } }2026.10.18又不知道多少年过去了依旧不会思路但是写出的代码比上次简洁算是有一点进步但不多。class Solution { public int maxProfit(int[] prices) { int result 0; int minPrice prices[0]; for (int i 1; i prices.length; i) { result Math.max(result, prices[i] - minPrice); minPrice Math.min(minPrice, prices[i]); } return result; } }