程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode 122 Best Time to Buy and Sell Stock II淺析(股票買入賣出的最佳時間 II)

LeetCode 122 Best Time to Buy and Sell Stock II淺析(股票買入賣出的最佳時間 II)

編輯:關於C++

翻譯

話說你有一個數組,其中第i個元素表示第i天的股票價格。

設計一個算法以找到最大利潤。你可以盡可能多的進行交易(例如,多次買入賣出股票)。

然而,你不能在同一時間來多次交易。(例如,你必須在下一次買入前賣出)。

原文

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like 
(ie, buy one and sell one share of the stock multiple times). 

However, you may not engage in multiple transactions at the same time 
(ie, you must sell the stock before you buy again).

分析

其實很簡單的一道題嘛,一開始想復雜了……

舉了栗子:

// 4 7 8 2 8
最大利潤很明顯是 (8 - 4) + (8 - 2) = 10
就因為這個式子讓我想復雜了:首先要找到一個極小值4,然後找到極大值8;然後找到極小值2,然後找到極大值8;balabala……

其實換一種思路,(7 - 4) + (8 - 7) + (8 - 2)
區別在於,直接將後一個數減前一個數就好了呀,只不過如果後一個數比前一個數小的話就不考慮而已。

代碼

class Solution {
public:
    int maxProfit(vector& prices) {
        size_t size = prices.size();
        if (size <= 1) return 0;
        int max = 0;
        for (int i = 1; i < size; ++i)
            max += prices[i] > prices[i - 1] ? prices[i] - prices[i - 1] : 0;
        return max;
    }
};
   
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved