Leetcode 123. Best Time to Buy and Sell Stock III JAVA语言

  1. 云栖社区>
  2. 博客>
  3. 正文

Leetcode 123. Best Time to Buy and Sell Stock III JAVA语言

科技小能手 2017-11-12 16:52:00 浏览548
展开阅读全文
1
2
3
4
5
6
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
 
Subscribe to see which companies asked this question.

题意:股票的买入卖出。你只有两次机会买入卖出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null || prices.length<2)return 0;
        //O(n^2)哎
        int sum=0;
        for(int i=1;i<prices.length;i++){
            int temp=getMax(prices,0,i)+getMax(prices,i+1,prices.length-1);
            if(temp>sum)sum=temp;
        }
        return sum;
    }
    public static int getMax(int[] prices,int left,int right){
        if(left>=prices.length)return 0;
        int Min=prices[left];
        int sum=0;
        for(int i=left+1;i<=right;i++){
            Min=Math.min(Min,prices[i]);
            sum=Math.max(sum,prices[i]-Min);
        }
        System.out.println(sum);
        return sum;
    // }
    // //first[i]从左往右遍历,表示到第i天时卖出能赚到的最大钱
    // int[] first=new int[prices.length];
    // //second[i]从右往左遍历,表示从第i天到最后一天能赚到的最大钱。本质还是分两部分计算。只不过是分开两次扫描数组
    // int[] second=new int[prices.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);
    // }
    // // for(int i=0;i<prices.length;i++){
    // //     System.out.println(first[i]);
    // // }
    // int max=prices[prices.length-1];
    // for(int i=prices.length-2;i>=0;i--){
    //     max=Math.max(max,prices[i]);
    //     second[i]=Math.max(second[i+1],max-prices[i]);
    // }
    // int ret=0;
    // for(int i=0;i<prices.length;i++){
    //     //System.out.println(second[i]);
    //     ret=Math.max(first[i]+second[i],ret);
    // }
     
    // return ret;
}
}

PS:解法一是直接以第i天为界,求两边的最大收益。但是需要O(N^2)。

优化:用俩数组,遍历两次。

本文转自 努力的C 51CTO博客,原文链接:http://blog.51cto.com/fulin0532/1910811


网友评论

登录后评论
0/500
评论
科技小能手
+ 关注