股票系列问题

发表于 | 阅读次数 | 阅读数 
Q1:nunms[i]代表股票的第i天的股价,求可获得的最大收益.交易一次.
public class besttimetobuyandsellstock {
    public int maxProfit(int[] prices) {
        if (prices.length==0||prices==null){
            return 0;
        }
        int result=0;
        int min=prices[0];
        for (int i=1;i<prices.length;i++){
          if (prices[i]>min){
              result=Math.max(result,prices[i]-min);//计算结果值
          }else {
              min= prices[i];//保存买入的那一天
          }

        }
        return result;
    }

    public int maxProfitII(int[] prices){
        if (prices.length==0||prices==null){
            return 0;
        }

        int local = 0;
        int global = 0;
        for (int i=1;i<prices.length;i++){
            local=Math.max(0,local+prices[i]-prices[i-1]);//局部最大值,注意表达式
            global= Math.max(global,local);//全局最大值
        }
        return global;
    }
}

  Q2:假设有一个数组，它的第i个元素是一个给定的股票在第i天的价格。
  设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。
  然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。
    public class BestTimetoBuyandSellStockII {
        public int maxProfit(int[] prices) {
            if (prices.length==0||prices==null){
                return 0;
            }
            int res = 0;
            for (int i=1;i<prices.length;i++){
                if (prices[i]-prices[i-1]>0){
                    res +=prices[i]-prices[i-1];//把所有的增长的都加起来,就是k次的最大利润
                }
            }
            return res;
        }
    }

假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。
设计一个算法来找到最大的利润。你最多可以完成两笔交易。
思想:二分  每一个i作为一个分界点   存储最大的利润
public class BestTimetoBuyandSellStockIII {
    public int maxProfit(int[] prices) {
        // write your code here
        if (prices.length==0||prices==null){
            return 0;
        }
        int length = prices.length;
        int[] first = new int[length];
        int[] second = new int[length];

        int min = prices[0];
        for (int i=1;i<prices.length;i++){
            min = Math.min(min,prices[i]);
            first[i]=Math.max(first[i-1],prices[i]-min);//从前往后计算出当前i的最大利润0-i的利润
        }

        int max = prices[length-1];
        for (int i = length-2;i>=0;i--){
            max = Math.max(max,prices[i]);
            second[i]=Math.max(second[i+1],max-prices[i]);//从后往前计算当前i的最大利润i-nums.length的利润
        }

        int maxprofit = 0;
        for (int i=0;i<length;i++){
            maxprofit=Math.max(maxprofit,first[i]+second[i]);
        }

        return maxprofit;
    }
}
0%