3,8,5,1,7,8
12
publicstaticint getmax(int [] prices ,int start ,int end )
{
int max = 0;
int min = prices[start];
for(int i=start+1;i<=end;i++)
{
if (prices[i]-min>max)
max = prices[i]-min;
if (prices[i]<min)
min = prices[i];
}
return max ;
}
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
public static int calculateMax(int[] prices)
{
int sum = 0;
for(int i=1;i<prices.length;i++)
{
int temp = getmax(prices,0,i)+getmax(prices,i,prices.length-1);
if(temp>sum)
sum = temp;
}
利用动态规划的思想。
public int calculateMax(int[] prices) { if(prices==null||prices.length<2) return 0; int len=prices.length; int[] left=new int[len]; left[0]=0; int min=prices[0]; int max=0; for(int i=1;i<len;i++){ if(prices[i]<min) min=prices[i]; if(prices[i]-min>max) max=prices[i]-min; left[i]=max; } int[] right=new int[len]; right[0]=0; int high=prices[len-1]; max=0; for(int i=len-2;i>=0;i--){ if(prices[i]>high) high=prices[i]; if(high-prices[i]>max) max=high-prices[i]; right[i]=max; } int result=0; for(int i=0;i<len;i++){ if(left[i]+right[i]>result) result=left[i]+right[i]; } return result; }
public class Solution { public int calculateMax(int[] prices) { if(prices==null || prices.length<2)return 0; 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 ret=0; for(int i=left+1;i<=right;i++){ Min=Math.min(prices[i],Min); ret=Math.max(ret,prices[i]-Min); } return ret; } }
/*思路: 可以将两次买股票看做数列中两组"递增"(不是真的递增) 数列 相当于求解一个index, 将数组分为两部分, 满足 max(prices[0:index)) - min(prices[0:index)) + max(prices[index:len]) - min(prices[index:len]) 最大; 设left[index]为index天前获得的最大利润 则有 left[index] = max(left[index -1], prices[index] - min); //min 为前index天最低价 设right[index] 为index天后获得的最大列润 则有 right[index] = max(right[index + 1], max - prices[index]) //max 为后index天最高价 找到另 right[index] + left[index] 取最大值得index即可 */ /* JavaScript 是个好东西 */ var maxProfit = function(prices) { var len = prices.length, min = prices[0], minprice = [], max = prices[len - 1], maxprice = [], res = 0; minprice[0] = 0; maxprice[len - 1] = 0; for(i = 1; i < len; i += 1){ minprice[i] = Math.max(minprice[i - 1], prices[i] - min); if(prices[i] < min){ min = prices[i]; } } for(i = len - 2; i >= 0; i -= 1){ maxprice[i] = Math.max(maxprice[i + 1], max - prices[i]); if(prices[i] > max){ max = prices[i]; } } for(i = 0; i < len; i += 1){ if(minprice[i] + maxprice[i] > res){ res = minprice[i] + maxprice[i]; } } return res; };
把代码简化了一些,看着比较舒畅。 public class Solution { /** * 计算你能获得的最大收益 * * @param prices Prices[i]即第i天的股价 * @return 整型 */ public int calculateMax(int[] prices) { int sum = 0,temp; for(int i=0; i<prices.length; i++){ temp = getMax(prices,0,i) + getMax(prices,i,prices.length-1); if(temp > sum) sum = temp; } return sum; } // 求最大start到end之间的最大利润函数 public int getMax(int[] prices, int start, int end){ int max = 0; int min = prices[start]; for(int i=start+1; i<=end; i++){ if(prices[i] < min) min = prices[i]; if(prices[i]-min > max) max = prices[i] - min; } return max; } }
//DP动态规划,时间复杂度o(n),空间复杂度o(2*n),这题还有将vec1的空间省去。 class Solution { public: int calculateMax(vector<int> prices) { vector<int> vec1(prices.size(),0), vec2(prices.size(),0); //vec1[i]表示从第1天到第i+1天的最大收益 //vec2[i]表示从第i+1天到最后一天的最大收益 int min=prices[0]; for(int i=1;i<prices.size();i++){ vec1[i]=vec1[i-1]; if(prices[i]-min>vec1[i]) vec1[i]=prices[i]-min; if(prices[i]<min) min=prices[i]; } int max=prices[prices.size()-1]; for(int i=prices.size()-2;i>=0;i--){ vec2[i]=vec2[i+1]; if(max-prices[i]>vec2[i]) vec2[i]=max-prices[i]; if(max<prices[i]) max=prices[i]; } int R=0; for(int i=0;i<prices.size();i++){ if(vec1[i]+vec2[i]>R) R=vec1[i]+vec2[i]; } return R; } };
int calculateMax(vector<int> prices) { int i,mr1 = 1000,max1=0,mr2 = -1000,max2=0; //强开上帝视角解法,即不断循环,人只能选择一次买入卖出时间,上帝可不断变换,根据当天股市情况调整自己之前的操作! for(i=0;i<prices.size();i++){ //第一次可买入的最低损失,损失少了也就相当于受益多,即抄底购入。 if( prices[i] < mr1 )//妈的,价格竟然比我第一次买的时候便宜,应该此时才买,损失更少。 mr1 = prices[i]; //若不购入的话,看看会不会是股票涨了,且涨幅获利大于上次的获利?趁机卖掉? else if( prices[i] - mr1 > max1 )//牛逼,涨了,卖掉。 max1 = prices[i] - mr1; //假设此时我们将第一次的股票已经抛掉,并在此刻购入,最低损失多少可购入。 if( max1 - prices[i] > mr2 )//挣了点小钱,找个价钱低的时候再次买入 mr2 = max1 - prices[i]; //第二次卖出可能获益的最大收入 else if( mr2 + prices[i] > max2 ) max2 = prices[i] + mr2; } return max2; } //解法二,遍历不同位置,每次将数组分为两部分,分别求其最大。 class Solution { public: int calculateMax(vector<int> prices) { int i,j,q,f,n,l1=0,r1=0,max=0,max1=0,min,max2=0; n = prices.size(); for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ if( prices[j]-1 < prices[j-1]){ max1 = prices[j-1] - prices[i]; max2 = 0; min = prices[j]; for(q=j+1;q<n;q++){ if(prices[q] - min > max2) max2 = prices[q] - min; else if(prices[q] < min) min = prices[q]; } if(max1+max2 > max) max = max1+max2; } } } if(prices[n-1] - prices[0] > max) max = prices[n-1] - prices[0]; return (max); } };
class Solution { public: /** * 计算你能获得的最大收益 * * @param prices Prices[i]即第i天的股价 * @return 整型 */ int calculateMax(vector<int> prices) { if(prices.empty()){ return 0; } // 动态规划 // g[i, j]表示0到i天,至多交易j次获得的最大收益 // l[i, j]表示0到i天,至多交易j次且最后一次在第j天卖出股票所获得的最大收益 // l[i, j] = max(l[i - 1, j] + diff, g[i - 1, j - 1] + max(diff, 0)) // g[i, j] = max(l[i, j], g[i - 1, j]) int K = 2; // 最多交易次数 vector<vector<int> > g(prices.size(), vector<int>(K, 0)); vector<vector<int> > l(prices.size(), vector<int>(K, 0)); for(int i = 0; i < prices.size(); i ++){ for(int j = 0; j < K; j ++){ if(i == 0){ l[i][j] = 0; g[i][j] = 0; } else if(j == 0){ int diff = prices[i] - prices[i - 1]; l[i][j] = max(l[i - 1][j] + diff, max(diff, 0)); g[i][j] = max(l[i][j], g[i - 1][j]); } else{ int diff = prices[i] - prices[i - 1]; l[i][j] = max(l[i - 1][j] + diff, g[i - 1][j - 1] + max(diff, 0)); g[i][j] = max(l[i][j], g[i - 1][j]); } } } return g.back().back(); } };
import java.util.*; public class Solution { /** * 计算你能获得的最大收益 * * @param prices Prices[i]即第i天的股价 * @return 整型 */ public int calculateMax(int[] prices) { int n=prices.length; int INF=-20000; int[][][] dp=new int[n+1][3][2]; //dp[i][k][0] 表示第k次交易,当前处于第i天,状态为手中无股的情况 //dp[i][k][1] 表示第k次交易,当前处于第i天,状态为手中有股的情况 //定义当前买入股票作为消耗交易次数的计数-1 dp[0][0][0]=0; dp[0][1][0]=0; for(int i=0;i<3;i++) dp[0][i][1]=INF; for(int k=1;k<=2;k++){ for(int i=1;i<=n;i++){ //无股 dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i-1]); //有股 dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i-1]); //System.out.println(dp[i][k][0]+"+"+dp[i][k][1]); } } return dp[n][2][0]; } }
import java.util.*; public class Solution { /** * 计算你能获得的最大收益 * * @param prices Prices[i]即第i天的股价 * @return 整型 */ public int calculateMax(int[] prices) { int i= 0,label = 0,maxnum = 0; if(prices.length == 1)return 0; if(prices.length == 2)return Math.max((prices[1] - prices[0]),0); int tmp1 = get_max(prices,0,prices.length - 1); for(i = 0;i<=prices.length-4;i++) for(label = i+1;label <= prices.length-3;label++){ int tmp = get_max(prices,i,label) + get_max(prices,label + 1, prices.length - 1); if(tmp>maxnum) maxnum = tmp; } return Math.max(maxnum,tmp1); } private int get_max(int[] array , int min, int max){ int i = 0,j = 0,maxnum = 0; for(i = min;i<= max;i++) for(j = i;j <= max;j++) if((array[j] - array[i]) > maxnum) maxnum = array[j] - array[i]; return maxnum; } 时间复杂度降不下来是我菜了,能编出来就不错了,说下思路:for(i = 0;i<=prices.length-4;i++) for(label = i+1;label <= prices.length-3;label++){ int tmp = get_max(prices,i,label) + get_max(prices,label + 1, prices.length - 1); if(tmp>maxnum) maxnum = tmp; }
这是核心,是用来算投资两次的,投资一次的很简单略过不讲。 也就是对0到length-4的每个数建立一个立一个label,用这个label将数组分成两个,分别计算局部的投资最大值。
int calculateMax(vector<int> prices) { int Len = prices.size(); int index = 1, max = 0; while (index < Len) { int tmp1, tmp2; tmp1 = tmp2 = 0; for (int i = 0; i < index; i++) { for (int j = i + 1; j < index + 1; j++) { if (tmp1 < prices[j] - prices[i]) tmp1 = prices[j] - prices[i]; } } for (int i = index + 1; i < Len - 1; i++) { for (int j = i + 1; j < Len; j++) { if (tmp2 < prices[j] - prices[i]) tmp2 = prices[j] - prices[i]; } } if (max < tmp1 + tmp2) max = tmp1 + tmp2; index++; } return max; }
分2部分求最大差值,方法笨,但好理解
package com.special.first;
import java.util.Scanner;
/**
* 小米03-中国牛市
*
* 其实就是两个区间的最大差值
* Create by Special on 2018/2/12 18:55
*/
public class Pro003 {
/**
* 获得该区间的最大差值
*
* 其实这可以优化,遇到时间限制再优化吧
* @param prices
* @param low
* @param high
* @return
*/
private static int getMaxDiff(int[] prices, int low, int high){
if(low >= high){ return 0; }
int result = 0;
for(int i = low; i <= high; i++){
for(int j = low; j < i; j++){
result = Math.max(result, prices[i] - prices[j]);
}
}
return result;
}
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
public static int calculateMax(int[] prices) {
int result = 0;
//把数组分成2个不相交的区间,分别求最大差值即可
for(int i = 1; i < prices.length - 1; i++){
result = Math.max(result, getMaxDiff(prices, 0, i) + getMaxDiff(prices,i + 1,
prices.length - 1));
}
return result;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int n = input.nextInt();
int[] nums = new int[n];
for(int i = 0; i < n; i++){
nums[i] = input.nextInt();
}
System.out.println(calculateMax(nums));
}
}
}
class Solution { public: /** * 计算你能获得的最大收益 * * @param prices Prices[i]即第i天的股价 * @return 整型 */ int calculateMax(vector<int> prices) { int buy1 = INT_MIN, sell1 = 0; int buy2 = INT_MIN, sell2 = 0; for(auto p:prices){ buy1 = max(buy1, -p); sell1 = max(sell1, buy1+p); buy2 = max(buy2, sell1-p); sell2 = max(sell2, buy2+p); } return sell2; } };
思路:股票只能在卖出去之后再买第二次,也就是说,原则上可以把数据划分成两部分。 每一部分分别求,且只能后项减去前项。 1.先把数据进行分割,分割的原则就是至少有一组其中至少有两个成员。 2.对两组(也可能是一组或一组半,即只有2跟3个元素,不过没关系)分别求出最佳收入。 但要注意,只能后项减去前项,即先买再卖。 3.求和,即max最大收入 4.递增移动分割点直至末尾,重复2,3。比较各分割点所得的max值 这种算法时间复杂度有点高,不过个人感觉容易理解些 int calculateMax(vector prices) { int n = prices.size(); int cut = 1, i = 0, j = 0; unsigned int max = 0, max1 = 0, max2 = 0; for (cut = 1; cut < n; cut++, max1 = 0, max2 = 0){ for (i = cut; i > 0; i--){ j = i -1; for (; j >= 0; j--){ if(max1 prices[j]) max1 = prices[i]-prices[j]; } } for (i = n-1; i > cut+1; i--){ j = i - 1; for (; j > cut; j--){ if(max2 prices[j]) max2 = prices[i]-prices[j]; } } if(max < max1+max2) max = max1 + max2; } return max; }
public int calculateMax(int[] prices) { int n = prices.length, m = 0, t, x = 0; int[] m1 = {prices[0], prices[0]}, m2 = {prices[n - 1], prices[n - 1]}; int[][] A = new int[n][2]; for (int i = 0; i < n; i++) { if (i > 0) { t = prices[i - 1]; if (t < m1[0]) { m1[0] = t; m1[1] = t; } if (t > m1[1]) m1[1] = t; t = m1[1] - m1[0]; x = t > x ? t : x; A[i][0] = x; } t = prices[n - i - 1]; if (t < m2[0]) m2[0] = t; if (t > m2[1]) { m2[1] = t; m2[0] = t; } t = m2[1] - m2[0]; m = t > m ? t : m; A[n - i - 1][1] = m; } for (int[] B : A) { t = B[0] + B[1]; if (t > m) m = t; } return m; }