Leetcode.122.Best Time to Buy an

题目

求股票获取最大利润, 可以进行多次交易.
给定一个数组, 数组表示第i天的股票价格. 买进后一天才能卖出, 卖出当天不能买入.
求获得的最大利润.

Input: [7,1,5,3,6,4]
Output: 7
Input: [1,2,3,4,5]
Output: 4
Input: [7,6,4,3,1]
Output: 0

思路

设置双指针, 每次只移动一个指针.
时间复杂度O(n)

int maxProfit(vector<int>& prices) {
    int n = (int)prices.size();
    if (n <= 1) return 0;
    int res = 0, l = 0;

    for(int i = 1;i < n; i++) {
        if (prices[i] <= prices[l]) {
            l = i;
        } else {
            int tmpR = prices[i];
            for(int j = i + 1;j < n; j++) {
                if (prices[j] >= tmpR) {
                    i = j;
                    tmpR = prices[j];
                } else {
                    break;
                }
            }
            res += prices[i] - prices[l];
            l = i + 1;
        }
    }
    return res;
}

总结

双指针方法关键在于选择到底移动那个变量.