题解 | #买卖股票的最好时机(一)#

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

https://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec

//本题用动态规划求解,暴力搜索最简单
//设记忆化数组 为 dp【i】【j】i为天数 j长度为2 【0】【1】 dp代表了i天所持钱数
//0 代表今天不持股 1代表今天持股 

//当今天不持股时 ,有两种情况 : 昨天不持股,或者昨天卖出
//状态转移方程为:dp[i][0] = Math.max[dp[i-1][0],dp[i-1][1] + prices[i]

//当今天持股时。有两种情况:昨天持股,或者昨天不持股,今天买入
//状态转移方程为:dp[i][1] = Math.max(dp[i-1][1], - prices[i]);
import java.util.*;


public class Solution {

    public int maxProfit (int[] prices) {
		//暴力搜索
       /* int ans = 0;
        int max = 0;
        int temp =   0;

        for (int i = 0; i < prices.length; i++) {
            for (int j = i+1; j < prices.length ; j++) {
                temp = prices[j] - prices[i];
                if (temp > max){
                    max = temp;
                }
            }
        }
        ans = max;
        return  ans;*/

		//动态规划
        if (prices.length < 2){
            return 0;
        }

        int[][] dp = new int[prices.length][2];
        int ans = 0;

        dp[0][0] = 0 ;
        dp[0][1] = -1 * prices[0];

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], - prices[i]);
            if (dp[i][0] > ans){
                ans = dp[i][0];
            }
        }
        return ans;
    }
}

动态规划题解 文章被收录于专栏

个人动态规划题解合集

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-15 17:46
暑期就挂了,秋招还有机会吗
大聪明777:研发提前批,14号刚开的,官网上面的配图上有写。提前批没过的话,秋招还可以投,不过前面的笔试/面试记录会被保留,供秋招参考
26届校招投递进展
点赞 评论 收藏
分享
牛客83700679...:简历抄别人的,然后再投,有反馈就是简历不行,没反馈就是学历不行,多投多改只要技术不差机会总会有的
点赞 评论 收藏
分享
zzzzhz:兄弟你先猛猛投简历至少三百家,能约到面试就去面。最近可以速成智能小车,智慧家居烂大街的项目,不需要自己写,只需要把里面的代码讲解看明白就行。把其中涉及到的八股文都拿出来单独背一下,我去年找工作就一个智能小车智慧家居找了10k差不多。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务