10

LeetCode-122-买卖股票的最佳时机 II

 2 years ago
source link: https://segmentfault.com/a/1190000041008352
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

LeetCode-122-买卖股票的最佳时机 II

发布于 11 月 24 日

买卖股票的最佳时机 II

题目描述：给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：贪心算法

因为不限制买卖的次数，要想得到多次交易的最大收益，实际上就是要得到正向的差值为正的累加和，因为对于任意一段正向正差值，实际上都可以假设做了一次买卖操作，如果是连续的正差值，则实际上可以看成是一次买卖，最小的数为买入操作，最大的数为卖出操作，所以根据贪心算法，具体处理过程如下：

  • 遍历数组，然后将每一段的正向差值为正数的差值都累加到收益里面，最后返回result即为预期最大的收益。

可以参考 LeetCode-121-买卖股票的最佳时机，应该还有动态规划的解法。

/**
 * 买卖股票的最佳时机 II
 */
public class LeetCode_122 {

    /**
     * 贪心算法
     *
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
        // 预期最大的收益值
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            // 获取每段的正向差值，即为实际的买卖操作
            result += Math.max(0, prices[i] - prices[i - 1]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] prices = new int[]{7, 1, 5, 3, 6, 4};
        // 测试用例，期望输出： 7
        System.out.println(maxProfit(prices));
    }
}

【每日寄语】 生活就是一半烟火，一半诗意。手执烟火谋生活，心怀诗意以谋爱。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK