let 121. Best Time to Buy and Sell Stock

xiaoxiao2021-02-28  11

主题思想: 直觉应该是到dp问题,不应该是O(n^2)的解法,所以寻找方法进行转化,最后发现如果计算每天的差值,就可以转化为求差值数组的连续最大子数组问题,因此问题得解。

AC 代码:

class Solution { public int maxProfit(int[] prices) { if(prices==null||prices.length==0) return 0; int [] diff=new int [prices.length-1]; for(int i=1;i<prices.length;i++){ diff[i-1]=prices[i]-prices[i-1]; } int sum=0; int mx=0; for(int i=0;i<diff.length;i++){ if(sum<0){ sum=diff[i]; }else{ sum+=diff[i]; } if(sum>mx)mx=sum; } return mx; } }
转载请注明原文地址: https://www.6miu.com/read-2350344.html

最新回复(0)