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