LeetCode 122. Best Time to Buy and Sell Stock II

Description:

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).

分析：

这道题没什么好说的，主要就是理解题意：要求我们买入新的股票前先卖掉拥有的股票，求能够赚多少钱。
这就是一个在数组中找多个递增数组的问题，只需一个时间复杂度为O(n)的算法遍历数组，比较相邻的数的大小，若后一个数大于前一个数，就把差值（即卖出后所赚的钱）加到res中。遍历结束后，返回该res即为结果。

代码如下：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 1) return 0;
        int res = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > prices[i - 1]) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
};
int main() {
	Solution s;
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	cout << s.maxProfit(nums) << endl;
	return 0;
}