.买卖股票的最佳时机 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你能选择某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。不限制买卖次数，问最大盈利，编写一个Java程序

题目可以使用贪心算法来解决。我们可以从第一天开始，如果当天的价格比前一天高，就在前一天买入，当天卖出，这样可以保证每次交易都是在最优的时机进行的。具体实现如下：

public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i-1]) { // 如果当天价格高于前一天价格
            profit += prices[i] - prices[i-1]; // 在前一天买入，当天卖出
        }
    }
    return profit;
}

时间复杂度为 O(n)，空间复杂度为 O(1)。

相关问题

C语言给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返

在C语言中，你可以使用动态规划(Dynamic Programming)来解决这个问题，这通常被称为「股票买卖」问题。这个算法的关键思路是维护两个变量：`min_price` 和 `max_profit`。

1. 初始化 `min_price` 为数组的第一个元素，因为初始状态下不可能有负利润；
2. 遍历数组，对于每个价格 `prices[i]`：
a. 如果 `prices[i]` 小于 `min_price`，更新 `min_price` 为当前值，因为在之后的日子里可能会有更低的价格。
b. 计算从当前天到目前为止的最高价格 `max_profit`，即 `prices[i] - min_price`。如果这个差值大于 `max_profit`，则更新 `max_profit`。
3. 当遍历完整个数组后，`max_profit` 就是你能获得的最大利润。

以下是算法的伪代码：

int maxProfit(int prices[], int n) {
    if (n <= 0) return 0; // 空数组或只有一天

    int min_price = prices[0];
    int max_profit = 0;

    for (int i = 1; i < n; i++) {
        min_price = min(min_price, prices[i]);
        max_profit = max(max_profit, prices[i] - min_price);
    }

    return max_profit;
}

使用kotlin解决这个问题：121. 买卖股票的最佳时机 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 示例 1： 输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2： 输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。 提示： 1 <= prices.length <= 105 0 <= prices[i] <= 104

可以使用动态规划的方法来解决此问题。定义状态 dp[i] 表示前 i 天的最大利润，其中第 i 天可以卖出股票，也可以不卖出股票。因此，状态转移方程为：

dp[i] = max(dp[i-1], prices[i]-minPrice)

其中，minPrice 表示前 i 天的最低股票价格。

最终的答案就是 dp 数组中的最大值。

下面是使用 Kotlin 实现的代码：

fun maxProfit(prices: IntArray): Int {
    var minPrice = Int.MAX_VALUE
    var maxProfit = 0
    for (price in prices) {
        minPrice = minOf(minPrice, price)
        maxProfit = maxOf(maxProfit, price - minPrice)
    }
    return maxProfit
}

可以通过以下代码进行测试：

fun main() {
    val prices1 = intArrayOf(7, 1, 5, 3, 6, 4)
    val prices2 = intArrayOf(7, 6, 4, 3, 1)
    println(maxProfit(prices1)) // 5
    println(maxProfit(prices2)) // 0
}

时间复杂度为 O(n)，空间复杂度为 O(1)。