[编程题]风口的猪-中国牛市
- 热度指数：31149 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。 给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，数组中第i个元素（prices[i]）代表该股票第i天的股价。 假设你一开始没有股票，但有至多两次买入1股而后卖出1股的机会，并且买入前一定要先保证手上没有股票。若两次交易机会都放弃，收益为0。 设计算法，计算你能获得的最大收益。 输入数值范围：2<=n<=100,0<=prices[i]<=100
示例1
输入
3,8,5,1,7,8
输出
12
class Solution {
public:
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
int calculateMax(vector<int> prices) {
int left[1000]={0};
left[0] = 0;
int curmin = prices[0];
int n = prices.size();
for(int i=1;i<n;i++){
curmin = min(curmin,prices[i]);
left[i] = max(left[i-1],prices[i]-curmin);
}
int right[1000]={0};
right[n-1] = 0;
int max_sell = prices[n-1];
for(int j=n-2;j>=0;j--){
max_sell = max(max_sell,prices[j]);
right[j] = max(right[j+1],max_sell-prices[j]);
}
int maxval = 0;
for(int i=0;i<n;i++){
maxval = max(maxval,left[i]+right[i]);
}
return maxval;
}
public:
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
int calculateMax(vector<int> prices) {
int left[1000]={0};
left[0] = 0;
int curmin = prices[0];
int n = prices.size();
for(int i=1;i<n;i++){
curmin = min(curmin,prices[i]);
left[i] = max(left[i-1],prices[i]-curmin);
}
int right[1000]={0};
right[n-1] = 0;
int max_sell = prices[n-1];
for(int j=n-2;j>=0;j--){
max_sell = max(max_sell,prices[j]);
right[j] = max(right[j+1],max_sell-prices[j]);
}
int maxval = 0;
for(int i=0;i<n;i++){
maxval = max(maxval,left[i]+right[i]);
}
return maxval;
}
};这个最后两个辅助数组的时候，买——卖，买——卖。所以第一个辅助数组应该是min_buy 从左至右，第二个辅助数组是max-sell 从右到左。
发表于 2016-08-29 15:55:43
回复(0)
更多回答
将问题划分为两部分即可。
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;
}
return
sum;
｝
发表于 2016-06-30 11:24:39
回复(18)
利用动态规划的思想。
首先从左往右扫描，先计算出子序列[0,...,i]中的最大利润，用一个left数组保存下来，时间是O(n)。第二步是从右往左逆向扫描，计算子序列[i,...,n-1]上的最大利润，用right数组保存下来，s时间是O(n)，同时结合left和right数组的结果就能计算最终的最大利润了，这一步也是O(n)。 所以最后算法的复杂度就是O(n)的。具体代码如下：
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;
}
编辑于 2016-04-10 15:41:10
回复(13)
确实，把区间分成两部分，分别求各自区间的最大收益。就和leetcode121题目一样了。
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;
}
}
发表于 2017-03-27 11:41:15
回复(0)
/*思路:
可以将两次买股票看做数列中两组"递增"(不是真的递增) 数列
相当于求解一个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;
};
编辑于 2016-08-11 19:51:42
回复(0)
{
intg[2+1] =
{0};//全局最优解
intl[2+1] =
{0};//局部最优解
for(inti=0;i<prices.size()-1;i++)
{
intdiff =
prices[i+1]-prices[i];
for(intj=2;j>=1;--j)
{
l[j] =
max(l[j]+diff,g[j-1]+max(diff,0));
g[j] =
max(g[j],l[j]);
}
}
returng[2];
}
发表于 2015-09-02 21:58:14
回复(1)
把代码简化了一些，看着比较舒畅。
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;
}
}
编辑于 2017-02-15 21:47:26
回复(1)
//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;
}
};
发表于 2016-08-16 09:43:02
回复(4)
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);
}
};
编辑于 2017-07-15 13:52:13
回复(2)
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();
}
};
发表于 2016-08-03 21:56:58
回复(0)
leetcode上的题目，代码如下，动态规划的知识。
class Solution {
public:
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
/*
设状态f(i)，表示区间[0;i](0 <= i <=
n-1)的最大利润，状态g(i)，表示区间[i;n-1](0 <= i <=
n - 1) 的最大利润，则最终答案为 max ff(i)+ g(i)g ; 0 <= i <= n - 1
允许在一天内买进又卖出，相当于不交易，因为题目的规定是最多两次，而不是一定要两次。
将原数组变成差分数组，本题也可以看做是最大 m 子段和，m =2，参考代码：
https://gist.github.com/soulmachine/5906637
*/
int calculateMax(vector<int> prices)
{
if(prices.size() < 2)
return 0;
const int n = prices.size();
vector<int> f(n,0);
vector<int> g(n,0);
int small = prices[0];
int peak = prices[n-1];
for(int i = 1;i < n;i++)
{
small = min(small,prices[i]);
f[i] = max(f[i-1],prices[i] - small);
}
for(int i = n-2;i >= 0;i--)
{
peak = max(peak,prices[i]);
g[i] = max(g[i],peak - prices[i]);
}
int max_profit = 0;
for(int i = 0;i < n;i++)
max_profit =max(max_profit,f[i]+g[i]);
return max_profit;
}
};
发表于 2016-03-14 16:04:34
回复(0)
动态规划，状态转移，具体多少次都可以实现，注意不合理的边界条件置为-inf，状态转移方程见代码
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];
}
}
发表于 2020-03-30 21:48:33
回复(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将数组分成两个，分别计算局部的投资最大值。
发表于 2018-08-15 15:44:31
回复(0)
开始是想用动态规划的，但是想了一上午也没想出比较好的规划方法。只能说自己算法还是不到家……没办法，就是使用了最简单暴力的方法——分割求值。方法如下：
1.设置分割点index，此点将数列分为两部分；
2.依次移动index点，每次遍历index点前后两部分，并将两部分的最大值进行求和记录；
3.当index移动至下一点并求和和，与上一次最大值进行比较，看是否是最大值。
代码如下，此代码时间复杂度是O(n3)，说实话有点高，写完代码后本来想优化一下，但是看了下数据量比较少就放弃了，这里有个优化大体思路：
由于前序列每次加新数值后其余数值是不需要进行再次求差，只需要跟新加进来的数求差后看与原来的相比那个更大即可；而对于后序列来说，由于该数字是与后方数字求和，因此不需要处理，例如：
3 8 5 1 7， index = 2
此时，前序列差值只有 8 - 5 = 3，后续列为 5 时最大差为 2，1 时 6。当index移动，不需要再次依次算差，只需要看是否 5 - 3 > 8 - 5，如果大替换，然后添加 5 - 8 = -3 进行最大比较即可，而 1 之后的差值与前面的数字没有任何影响，可以无视。这样的话避免的许多次重复计算，时间复杂度可以降至O(n2)。优化时关于后续最大值保存问题可以用栈依次保存每次最大值，这样在前序列提走后序列的最前面一个值时可以更新后序列的最大值。哪位小伙伴如果感兴趣写好了代码麻烦留一下评论，未优化个人代码如下：
1.设置分割点index，此点将数列分为两部分；
2.依次移动index点，每次遍历index点前后两部分，并将两部分的最大值进行求和记录；
3.当index移动至下一点并求和和，与上一次最大值进行比较，看是否是最大值。
代码如下，此代码时间复杂度是O(n3)，说实话有点高，写完代码后本来想优化一下，但是看了下数据量比较少就放弃了，这里有个优化大体思路：
由于前序列每次加新数值后其余数值是不需要进行再次求差，只需要跟新加进来的数求差后看与原来的相比那个更大即可；而对于后序列来说，由于该数字是与后方数字求和，因此不需要处理，例如：
3 8 5 1 7， index = 2
此时，前序列差值只有 8 - 5 = 3，后续列为 5 时最大差为 2，1 时 6。当index移动，不需要再次依次算差，只需要看是否 5 - 3 > 8 - 5，如果大替换，然后添加 5 - 8 = -3 进行最大比较即可，而 1 之后的差值与前面的数字没有任何影响，可以无视。这样的话避免的许多次重复计算，时间复杂度可以降至O(n2)。优化时关于后续最大值保存问题可以用栈依次保存每次最大值，这样在前序列提走后序列的最前面一个值时可以更新后序列的最大值。哪位小伙伴如果感兴趣写好了代码麻烦留一下评论，未优化个人代码如下：
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;
}
发表于 2018-03-13 12:37:03
回复(0)
分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));
}
}
}
发表于 2018-02-12 19:42:31
回复(0)
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;
}
};
发表于 2017-11-20 13:03:23
回复(0)
思路：股票只能在卖出去之后再买第二次，也就是说，原则上可以把数据划分成两部分。
每一部分分别求，且只能后项减去前项。
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;
}
编辑于 2017-09-08 15:46:37
回复(0)
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;
}
发表于 2017-04-20 22:50:16
回复(0)
有两次买进卖出，就将数组分成两部分，求各自部分的最大收益
import java.util.*;
public class Solution {
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
public int calculateMax(int[] prices) {
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 int getMax(int[] prices,int left,int right)
{
if(left>=prices.length)
return 0;
int max=0;
int min=prices[left];
for(int i=left+1;i<=right;i++)
{
if(prices[i]>min)
{
if(max<(prices[i]-min))
max=prices[i]-min;
}
else
min=prices[i];
}
return max;
}
}
发表于 2017-03-16 11:07:59
回复(0)
//比较笨但是好理解的思路（已经通过），遍历时间点
public int calculateMax(int[] prices) {
List<Integer> priceList = new ArrayList<Integer>();
for (int a : prices) {
priceList.add(a);
}
int maxPrice = 0;
if (prices.length > 2) {
//遍历时间点，然后分割
for (int i = 1; i < prices.length; i++) {
List<Integer> first = priceList.subList(0, i);
List<Integer> second = priceList.subList(i-1, priceList.size());
int firstPrice = maxPrice(first);
int secondPrice = maxPrice(second);
maxPrice = (firstPrice + secondPrice) > maxPrice ? (firstPrice + secondPrice) : maxPrice;
}
} else {
//等于2天的直接计算
maxPrice = maxPrice(priceList);
}
//System.out.println(maxPrice);
return maxPrice;
}
/**
* 获取时间段的最大收益
*/
public int maxPrice(List<Integer> list) {
int maxPrice = 0;
for (int i = 0; i < list.size() - 1; i++) {
int buy = list.get(i);
for (int j = i + 1; j < list.size(); j++) {
int sell = list.get(j);
maxPrice = (sell - buy) > maxPrice ? (sell - buy) : maxPrice;
}
}
return maxPrice;
}
public int calculateMax(int[] prices) {
List<Integer> priceList = new ArrayList<Integer>();
for (int a : prices) {
priceList.add(a);
}
int maxPrice = 0;
if (prices.length > 2) {
//遍历时间点，然后分割
for (int i = 1; i < prices.length; i++) {
List<Integer> first = priceList.subList(0, i);
List<Integer> second = priceList.subList(i-1, priceList.size());
int firstPrice = maxPrice(first);
int secondPrice = maxPrice(second);
maxPrice = (firstPrice + secondPrice) > maxPrice ? (firstPrice + secondPrice) : maxPrice;
}
} else {
//等于2天的直接计算
maxPrice = maxPrice(priceList);
}
//System.out.println(maxPrice);
return maxPrice;
}
/**
* 获取时间段的最大收益
*/
public int maxPrice(List<Integer> list) {
int maxPrice = 0;
for (int i = 0; i < list.size() - 1; i++) {
int buy = list.get(i);
for (int j = i + 1; j < list.size(); j++) {
int sell = list.get(j);
maxPrice = (sell - buy) > maxPrice ? (sell - buy) : maxPrice;
}
}
return maxPrice;
}
编辑于 2016-11-22 19:14:25
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-16 17:01:46
-
2022-09-14 09:34:24 -
2022-09-13 19:45:47
-
2022-09-13 15:50:03
-
2022-09-12 23:06:37
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
