买卖股票的最好时机(二)

[编程题]买卖股票的最好时机(二)

热度指数：42047 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1. 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票

2. 如果不能获取收益，请返回0

3. 假设买入卖出均无手续费

数据范围： $1 \le n \le 1 \times 10^5$ ， $1 \le prices[i] \le 10^4$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

[8,9,2,5,4,7,1]

输出

说明

在第1天(股票价格=8)买入，第2天(股票价格=9)卖出，获利9-8=1
在第3天(股票价格=2)买入，第4天(股票价格=5)卖出，获利5-2=3
在第5天(股票价格=4)买入，第6天(股票价格=7)卖出，获利7-4=3
总获利1+3+3=7，返回7

示例2

输入

[5,4,3,2,1]

输出

说明

由于每天股票都在跌，因此不进行任何交易最优。最大收益为0。

示例3

输入

[1,2,3,4,5]

输出

说明

第一天买进，最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。

备注:

总天数不大于200000。保证股票每一天的价格在[1,100]范围内。

算法知识视频讲解

算帝

int maxProfit(int* prices, int n ) {
    int sum = 0;
    int i = 0;
    if(n < 2) return 0;
    while(i < n-1) {    //将股票价格画成折线图，计算上升沿的总长度
        if(prices[i] < prices[i+1]) {
            sum += prices[i+1] - prices[i];
        }
        i++;
    }
    return sum;
}

发表于 2023-01-08 23:25:54 回复(0)