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

可以使用贪心算法来解决这个问题。我们可以在每次价格上涨时买入，价格下跌时卖出。

具体来说，我们可以从第二天开始遍历价格数组，如果当前价格比前一天高，就在前一天买入，然后在当天卖出。累加每次交易的盈利即可。如果当前价格比前一天低，就不进行任何操作。

Java代码如下：

public int maxProfit(int[] prices) {
    int maxProfit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            maxProfit += prices[i] - prices[i - 1];
        }
    }
    return maxProfit;
}

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

相关问题

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

在C语言中，你可以使用动态规划（Dynamic Programming）来解决这个问题，也就是著名的「股市买卖」问题。以下是基本的算法步骤：

1. 初始化两个变量 `min_price` 和 `max_profit`，分别表示到目前为止的最低价格和最大利润。初始化时，假设第一天的最低价格为第一项 `prices[0]`，最大利润为0。

2. 遍历整个数组 `prices`，从第二天开始：
- 如果当前价格 `prices[i]` 小于 `min_price`，则更新 `min_price` 为这个价格。因为如果这一天的价格更低，那么我们可以在这个价格买入，等待更高价格卖出。
- 否则，计算 `prices[i] - min_price`，这个差值代表了在 `min_price` 这一天买入并在 `prices[i]` 这一天卖出可以获得的利润。取这个值和当前的 `max_profit` 中较大的作为新的 `max_profit`。

3. 当遍历完整个数组后，`max_profit` 就是你能获取的最大利润。

下面是伪代码形式的算法：

int maxProfit(int prices[], int n) {
    int min_price = prices[0];
    int max_profit = 0;

    for (int i = 1; i < n; i++) {
        if (prices[i] < min_price) {
            min_price = prices[i];
        } else {
            int profit_here = prices[i] - min_price;
            max_profit = MAX(max_profit, profit_here);
        }
    }

    return max_profit;
}

给定一个数组 prices ，它的第 i 个元素prices[i] 表示一支给定股票第 i 天的价格。 你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

### 回答1：
题目要求设计一个算法，能够求出给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一天卖出该股票。设计一个算法来计算你所能获得的最大利润。如果你不能获得任何利润，返回 0。

具体实现方法可以通过遍历数组来找到数组中最小的数，然后再寻找它之后的最大值，两者相减即为所求的利润最大值，如果没有利润，则返回值为0。可以通过交易中获得的最大利润来证明算法的正确性。

### 回答2：
这道题目是一道典型的贪心算法，并且有一个非常巧妙的办法可以在遍历过程中同时计算出最大利润。

我们记录两个整数变量 minPrice 和 maxProfit，其中 minPrice 表示数组 prices 中当前遍历到的最小值，而 maxProfit 表示当前最大利润。遍历数组时，我们每遍历到一个数字，就用当前价格减去 minPrice 得到一个当前的利润，并将这个利润和当前的 maxProfit 取一个最大值，然后继续向后遍历。如果当前价格比 minPrice 还要小，那么我们就更新 minPrice 为当前价格，因为我们希望能够在价格最低的时候买入。

最后遍历完成后，maxProfit 就是我们要求的最大利润。如果 maxProfit 小于等于 0，那么说明我们无法获取任何利润，因此返回 0。

下面给出 Java 代码实现：

class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
}
}
return maxProfit;
}
}

### 回答3：
题目描述

给定一个数组prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。

思路分析

本题可以使用贪心算法来解决。假如我们在买入时选择在最低点购买，那么在之后的每一天里，只要股票价格高于买入价，我们就可以选择在当前天卖出股票，获取最大利润。

因此，我们只需要通过一次遍历数组，找到最低点和最高利润即可。假设low表示当前最低点，max_profit表示当前最高利润，那么对于数组中的每一个元素，我们不断更新low和max_profit即可。

代码实现

class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1) { // 特判数组长度小于等于1的情况
return 0;
}
int low = prices[0]; // 初始化最低价格为数组的第一个元素
int max_profit = 0; // 初始化最大利润为0
for(int i = 1; i < prices.size(); i++) {
if(prices[i] < low) { // 如果当前价格低于最低价格，更新最低价格
low = prices[i];
}else { // 如果当前价格高于最低价格，计算当前利润并更新最大利润
int cur_profit = prices[i] - low;
if(cur_profit > max_profit) {
max_profit = cur_profit;
}
}
}
return max_profit;
}
};