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

买卖股票的最好时机

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

贪心或者dp

设当前天为为i,那么在i天,我们可以买或者不买,买的话应该用prices[i] - min(prices[j]) 0 <= j < i
import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int n = prices.length;
        int a = 0;
        int b = 1000000;
        for(int i = 0;i < n;i++){
            a = Math.max(a,prices[i] - b);
            b = Math.min(b,prices[i]);
        }
        return a;
    }
}
dp:设f[i][2]:为[0,i]所能买卖股票的集合,0为买入,1为卖出
f[i][0] = min(f[i - 1][0],prices[i])
f[i][1] = max(f[i - 1][1],prices[i] - f[i - 1][0])
import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int n = prices.length;
        int f[][] = new int[n + 10][2];
        f[0][0] = 1000000;
        f[0][1] = 0;
        for(int i = 0;i < n;i++){
            //为了防止下标越界,将i统一+1即可
            f[i + 1][0] = Math.min(f[i][0],prices[i]);
            f[i + 1][1] = Math.max(f[i][1],prices[i] - f[i][0]);
        }
        return f[n][1];
    }
}
全部评论

相关推荐

湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
每晚夜里独自颤抖:要求太多的没必要理
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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