首页 > 试题广场 >

买卖股票的最好时机 ii

[编程题]买卖股票的最好时机 ii

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

假设你有一个数组，其中第 $i\$ 个元素表示某只股票在第 $i\$ 天的价格。
设计一个算法来寻找最大的利润。你可以完成任意数量的交易(例如，多次购买和出售股票的一股)。但是，你不能同时进行多个交易(即，你必须在再次购买之前卖出之前买的股票)。

示例1

输入

[1,4,2]

输出

说明

第一天买入，第二天卖出，收益为4-1=3。

示例2

输入

[1,2,1,4]

输出

说明

第一天买入，第二天卖出，第三天买入，第四天卖出，收益为(2-1)+(4-1)=4。

算法知识视频讲解

Java

花落梦里

//在自己电脑上运行结果正确，但是在平台上运行保错

	请检查是否存在数组越界等非法访问情况



	case通过率为0.00% Exception in thread "main" java.lang.StackOverflowError at Solution.getProfit(Solution.java:33) 

import java.util.*;
public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    static int maxP=0;
    static public int maxProfit (int[] prices) {
        // write code here
        getProfit(prices,0,false,0);//初始化buy=false未购买。cost=赚的钱
        return maxP;
    }
     static public int getProfit(int[] prices, int day,boolean buy,int cost){
        if(day==prices.length-1){//假设还有一天买卖的机会
            if(buy){
                cost=cost+prices[day];//一定会卖出去
            }
            if(cost>maxP)
                maxP=cost;
            return cost;
        }

        int cost1,cost2;
        //遍历所有的情况
        if(buy){//如果已经买了，则可能卖，也可能不卖。
            cost1=getProfit(prices,day+1,false,cost+prices[day]);//卖出去
            cost2=getProfit(prices,day+1,true,cost);//没有卖
        }
        else{//如果还没买，可能买也可能不买。
            cost1=getProfit(prices,day+1,false,cost);//没有买
            cost2=getProfit(prices,day+1,true,cost-prices[day]);//买了
        }
        return Math.max(cost1,cost2);

    }

}

编辑于 2020-11-09 20:14:36 回复(1)

Java

LUA201905072300882

public class Solution {
    public int maxProfit(int[] prices) {
        //不限次数的交易，最大利润就是每次买入都是涨价的，所有涨的都有份，跌的时候早就卖了
        int max=0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]>prices[i-1])
                max += prices[i]-prices[i-1];
        }
        return max;
    }
}

编辑于 2020-04-29 16:02:29 回复(0)

Java

AriesLi

class Solution {
    /**
     *  继续上一题思路，继续用转移方程
     *  假设第i天持有股票的收益为f(i,1),未持有的收益为f(i,0)
     *  f(i,1) = max(f(i-1, 1), f(i-1, 0)-prices[i])
     *  f(i,0) = max(f(i-1, 0), f(i-1, 1)+prices[i])
     *  f(0,0) = 0, f(0,1)=-prices[0];
     *  还有一个思路是遍历判断前后两天的收益，是正的就累计
     *  因为不限制交易次数，可以在跌了前卖出，涨之前买入
     *  吃掉所有利差
     */
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int i0=0, i1=-prices[0];
        for(int i=0; i<prices.length; i++){
            int j0 = Math.max(i0, i1+prices[i]);
            int j1 = Math.max(i1, i0-prices[i]);
            i0=j0;
            i1=j1;
        }
        return i0;
    }
}

发表于 2020-01-08 15:26:11 回复(0)

Java

Mono_Chrome

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

发表于 2019-11-06 16:09:44 回复(0)

Java

HW柯可

public class Solution {
//相邻两天的股票价格如果是递增关系，就第一天买入，第二天就卖出，这样可以得到累积获得的利润最大
    public int maxProfit(int[] prices) {
        if(prices.length < 2)
            return 0;
        int max_profit = 0;
        int buy = prices[0];
        for(int i = 1; i < prices.length; i++){
            if(prices[i] > buy){
                max_profit += prices[i] - buy;
            }
            buy = prices[i];
        }
        return max_profit;
    }
}

编辑于 2019-07-24 15:12:07 回复(0)

Java

回去等通知吧

//一个简单的题目...
public int maxProfit(int[] prices) {
        int res = 0;
        for(int i = 1;i< prices.length; i++){
            if(prices[i] > prices[i - 1]){
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }

发表于 2018-07-20 10:46:11 回复(0)

Java

七仔0312

如果数组递增，如1,3,5，则可以看做连续买入，也就是5-1=5-3+3-1。

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

发表于 2018-03-29 21:39:28 回复(0)

Java

WalterCapable

if (prices.length <= 1) {
            return 0;
        }
        int min = prices[0];
        int max = prices[0];
        int profit = 0;
        for (int i : prices
                ) {
            if (i < max) {
                profit += max - min;
                max = i;
                min = i;
            }
            if (i < min) {
                // buy day
                min = i;
            }
            if (i > max) {
                // sell day
                max = i;
            }
        }
        if (max>min)
            profit += max - min;
        return profit;

拿到区间的最大值和最小值，在降价的时候出手。然后重新计算买入点和卖出点，再卖出...

发表于 2017-12-26 15:54:28 回复(0)

Java

傻傻傻傻

//一开始题目都没读懂，23333
public class Solution {
    public int maxProfit(int[] prices) {
        //可以买卖多次，波谷买入，波峰卖出，即可实现利益最大化
        if (prices == null || prices.length < 2)
            return 0;
        int sum = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                sum += (prices[i] - prices[i - 1]);
        }
        return sum;
    }
}

发表于 2017-11-27 16:43:46 回复(0)

Java

唐唐苦不苦呀

//因为题目中没有限定买卖次数，所以这里只要有收益就选择卖出，再买。就可以！
public class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int currSum=0;
        int maxSum=0;
        for(int i=1;i<n;i++){
            currSum=Math.max(currSum,currSum+prices[i]-prices[i-1]);
            maxSum=Math.max(currSum,maxSum);
        }
        return maxSum;
    }
}

编辑于 2017-11-26 23:21:49 回复(0)

Java

阿拉要洗澡

public class Solution {

public int maxProfit(int[] prices) {

if(prices.length==0){

return 0;

}

int curMax=0;

int curMin=prices[0];

int profit=0;

for(int i=1;i<prices.length;i++){

if(prices[i] < prices[i-1]){

profit+=curMax;

curMax=0;

curMin=prices[i];

continue;

}

curMin=Math.min(curMin, prices[i]);

curMax=Math.max(curMax,prices[i]-curMin);

}

profit+=curMax;

return profit;

}

发表于 2017-08-07 11:33:55 回复(0)

Java

pp11

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

编辑于 2017-07-30 17:00:25 回复(0)

Java

唛闹

计算第二天与第一天的利润值,只要为正就加到res中.

        if(prices == null)return 0;
        int res = 0;
        int temp = 0;
        for (int i = 1; i < prices.length; i++) {
            temp = prices[i]-prices[i-1];
            res +=temp>0?temp:0;
        }
        return res;

发表于 2017-07-30 14:51:50 回复(0)

Java

ephonzhang

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

编辑于 2017-06-20 23:40:20 回复(0)

Java

Holiday_12138

public class Solution {//所有递增子区间
    public int maxProfit(int[] prices) {
        int res=0;
        int index=0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]<prices[i-1]){
                res+=(prices[i-1]-prices[index]);
                index=i;
            }
            if(i==prices.length-1){
                res+=(prices[i]-prices[index]);
            }
        }
        return res;
    }
}

发表于 2017-05-23 15:38:52 回复(0)

Java

城市里的养猫者

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