模板建站是什么意思,中国电信企业邮箱登录入口,网站在百度找不到了,珠海建站论坛买卖股票的最佳时机 II
给你一个整数数组 prices #xff0c;其中 prices[i] 表示某支股票第 i 天的价格。
在每一天#xff0c;你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买#xff0c;然后在 同一天 出售。
返回 你能获得的…买卖股票的最佳时机 II
给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1
输入prices [7,1,5,3,6,4] 输出7 解释在第 2 天股票价格 1的时候买入在第 3 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4 。 随后在第 4 天股票价格 3的时候买入在第 5 天 股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3 。 总利润为 4 3 7 。
解题思路
这是一个典型的贪心算法问题。
可以贪心地选择每次股票价格下跌之前卖出上涨之前买入。因此只需计算所有相邻价格之间的差价且如果差价大于 0 则将其累加到最大利润中。
java实现
public class BestTimeToBuyAndSellStockII {public int maxProfit(int[] prices) {int maxProfit 0;for (int i 1; i prices.length; i) {int profit prices[i] - prices[i - 1];if (profit 0) {maxProfit profit;}}return maxProfit;}public static void main(String[] args) {BestTimeToBuyAndSellStockII maxProfit new BestTimeToBuyAndSellStockII();int[] prices1 {7, 1, 5, 3, 6, 4};int result1 maxProfit.maxProfit(prices1);System.out.println(Test Case 1:);System.out.println(Prices: [7, 1, 5, 3, 6, 4]);System.out.println(Max Profit: result1); // Expected: 7int[] prices2 {1, 2, 3, 4, 5};int result2 maxProfit.maxProfit(prices2);System.out.println(\nTest Case 2:);System.out.println(Prices: [1, 2, 3, 4, 5]);System.out.println(Max Profit: result2); // Expected: 4int[] prices3 {7, 6, 4, 3, 1};int result3 maxProfit.maxProfit(prices3);System.out.println(\nTest Case 3:);System.out.println(Prices: [7, 6, 4, 3, 1]);System.out.println(Max Profit: result3); // Expected: 0}
}时间空间复杂度
时间复杂度 遍历一次股票价格数组时间复杂度为 O(n)其中 n 是数组的长度。空间复杂度 使用了常数级的额外空间空间复杂度为 O(1)。
