校园网站建设建议,安徽天筑建设集团网站,巴中城乡和住房建设厅网站,怎样注册一个自己的网站给定一个数组#xff0c;它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易#xff08;多次买卖一支股票#xff09;。
注意#xff1a;你不能同时参与多笔交易#xff08;你必须在再次购买前出售掉…给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
示例 1:
输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。 随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6-3 3 。 示例 2:
输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。 注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。 因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。 示例 3:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 思路
情况一今天买明天卖收益为prices[i]-prices[i-1]
情况二连续上涨则在第一天买在上涨到顶峰的最后一天卖掉
情况三连续下降 则不买卖收益最大不会亏钱。 算法流程
遍历整个股票交易日价格列表 price策略是所有上涨交易日都买卖赚到所有利润所有下降交易日都不买卖永不亏钱。 设 tmp 为第 i-1 日买入与第 i 日卖出赚取的利润即 tmp prices[i] - prices[i - 1] 当该天利润为正 tmp 0则将利润加入总利润 profit当利润为 0 或为负则直接跳过 遍历完成后返回总利润 profit。 复杂度分析
时间复杂度 O(N)只需遍历一次price 空间复杂度 O(1)变量使用常数额外空间。
提交的代码
class Solution { public int maxProfit(int[] prices) { int sum0; for(int i1;iprices.length;i) { if(prices[i]-prices[i-1]0) { sumprices[i]-prices[i-1]; } } return sum; } }
完整的代码 public class Solution122 { public static int maxProfit(int[] prices) { int sum0; for(int i1;iprices.length;i) { if(prices[i]-prices[i-1]0) { sumprices[i]-prices[i-1]; } } return sum; } public static void main(String[] args) { int nums[] {7,1,5,3,6,4}; System.out.println(maxProfit(nums)); } }
