logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
Leetcode 上面的 Best Time to Buy and Sell Stock III
avatar
Leetcode 上面的 Best Time to Buy and Sell Stock III# JobHunting - 待字闺中
w*4
1 楼
总是过不了Large Judge。
各位大侠有更好的解法吗？
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int max =0;
for (int i = 0;iint value = maxProfit(prices,i);
max = Math.max(value, max);
}
return max;
}

private int maxProfit(int[] prices, int index){
int maxfront =0;
int min =0;
int maxend =0;
for (int i=0;i<=index;i++){
if (prices[i]min = i;
int diff = prices[i] - prices[min];
if (diff >maxfront){
maxfront = diff;
}
}
min = index+1;
for (int i = index+1;iif (prices[i]min = i;
int diff = prices[i] - prices[min];
if (diff >maxend){
maxend = diff;
}
}
return maxfront + maxend;
}
}
avatar
j*g
2 楼
large judge过了
class Solution {
public:
int maxProfit(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(prices.size()<=1)
return 0;

vector diff;
for(int i=0;i{
diff.push_back(prices[i+1]-prices[i]);
}

int posi =0;
int nega =0;
vector inter;
for(int j=0;j{
if(diff[j]>0){
if(nega<0){
inter.push_back(nega);
nega=0;
}
posi+=diff[j];
}
else if(diff[j]<0){
if(posi>0){
inter.push_back(posi);
posi=0;
}
nega+=diff[j];
}
}

if(nega<0){
inter.push_back(nega);
nega=0;
}
if(posi>0){
inter.push_back(posi);
posi=0;
}

int len = inter.size();
if (len==0)
return 0;

int maxb =0;
if(inter[0]>0){
if(len==1)
return inter[0];
for(int i=1;imaxb=max(cal(inter, i),maxb);
}
}else{
if(len==1)
return 0;
for(int i=0;imaxb=max(cal(inter, i),maxb);
}
}

return maxb;
}


int cal(vector &inter, int index) {
int left=0;
int right =0;
int suml =0;
int sumr=0;
for(int i =0;i{
if(suml+inter[i]>0){
suml+=inter[i];
if(suml>left)
left=suml;
}
else
suml=0;
}

for(int i =index;i{
if(sumr+inter[i]>0){
sumr+=inter[i];
if(sumr>right)
right=sumr;
}
else
sumr=0;
}

return left+right;
}
};
avatar
p*2
3 楼
我刚刚练了练
public int maxProfit(int[] prices)
{
if(prices==null || prices.length==0)
return 0;

int len=prices.length;
int[] dp1=new int[len];
int[] dp2=new int[len];
int max=prices[len-1];
int min=prices[0];

for(int i=1;i {
min=Math.min(min,prices[i]);
dp1[i]=Math.max(dp1[i-1],prices[i]-min);
}
for(int i=len-2;i>=0;i--)
{
max=Math.max(max, prices[i]);
dp2[i]=Math.max(dp2[i+1],max-prices[i]);
}

int ans=0;
for(int i=0;ians=Math.max(ans, dp1[i]+dp2[i]);
return ans;
}
avatar
c*5
4 楼
Hi,
I don't understand this part:
for(int i=0;ians=Math.max(ans, dp1[i]+dp2[i]);
Could you explain it a little more?
Thank you very much.

【在 p*****2 的大作中提到】
: 我刚刚练了练
: public int maxProfit(int[] prices)
: {
: if(prices==null || prices.length==0)
: return 0;
:
: int len=prices.length;
: int[] dp1=new int[len];
: int[] dp2=new int[len];
: int max=prices[len-1];
avatar
e*s
5 楼
2爷V5！

【在 p*****2 的大作中提到】
: 我刚刚练了练
: public int maxProfit(int[] prices)
: {
: if(prices==null || prices.length==0)
: return 0;
:
: int len=prices.length;
: int[] dp1=new int[len];
: int[] dp2=new int[len];
: int max=prices[len-1];
avatar
j*g
6 楼
I think dp1[i] keeps the best transaction whose selling happens on or before
day i, dp2[i] keeps the best transaction whose buying happens on or after
day i.
Then Max(dp1[i] + dp2[i]) returns the maximum sum of two transactions. One
transaction finishes on or before day i, another one finishes after day i.

【在 c******5 的大作中提到】
: Hi,
: I don't understand this part:
: for(int i=0;i: ans=Math.max(ans, dp1[i]+dp2[i]);
: Could you explain it a little more?
: Thank you very much.
avatar
t*n
7 楼
发个自己的吧，请指正...努力学习2爷中...
int maxProfit3(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(!prices.size())
return 0;
vector a;
vector b;
vector::iterator it;
int min = prices[0];
int profit = 0;
for(it=prices.begin(); itif(*itmin = *it;
int temp = *it - min;
if(temp > profit){
a.push_back(temp);
profit = temp;
}
else
a.push_back(profit);
}

int max = prices[prices.size()-1];
profit = 0;
for(it=prices.end()-1;it>= prices.begin();it--){
if(*it > max)
max = *it;
int temp = max - *it ;
if(temp > profit){
b.push_back(temp);
profit = temp;
}
else
b.push_back(profit);
}
reverse(b.begin(),b.end());

int maxProfit = 0;
int length = a.size();
for(int i=-1; iint temp1 = (i==-1?0:a[i]);
int temp2 = ((i==a.size()-1)?0:b[i+1]);
int temp = temp1+temp2;
if(temp > maxProfit)
maxProfit = temp;
}
return maxProfit;
}
avatar
c*t
8 楼
再试试简化简化

【在 t*********n 的大作中提到】
: 发个自己的吧，请指正...努力学习2爷中...
: int maxProfit3(vector &prices) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: if(!prices.size())
: return 0;
: vector a;
: vector b;
: vector::iterator it;
: int min = prices[0];
avatar
p*g
9 楼
int maxProfit(vector &prices) {
int size = prices.size();
if (size<=1)
return 0;

int* front = new int [size];
front[0] = 0;
int minp = prices[0];

for (int i=1; iint p = prices[i];
front[i] = max(front[i-1], p-minp);
minp = min(minp, p);
}

int* back =new int[size];
back[size-1] = 0;
int maxp = prices[size-1];

for (int i=size-2; i>=0; i--) {
int p = prices[i];
back[i] = max(back[i+1], maxp-p);
maxp = max(maxp, p);
}

int rv = back[0];
for (int cut = 1; cutrv = max(rv, (front[cut]+back[cut+1]));
}

return rv;
}

【在 w**********4 的大作中提到】
: 总是过不了Large Judge。
: 各位大侠有更好的解法吗？
: public class Solution {
: public int maxProfit(int[] prices) {
: if (prices == null || prices.length == 0)
: return 0;
: int max =0;
: for (int i = 0;i: int value = maxProfit(prices,i);
: max = Math.max(value, max);
avatar
p*g
10 楼
int maxProfit(vector &prices) {
int size = prices.size();
if (size<=1)
return 0;

int* front = new int [size];
front[0] = 0;
int minp = prices[0];

for (int i=1; iint p = prices[i];
front[i] = max(front[i-1], p-minp);
minp = min(minp, p);
}

int* back =new int[size];
back[size-1] = 0;
int maxp = prices[size-1];

for (int i=size-2; i>=0; i--) {
int p = prices[i];
back[i] = max(back[i+1], maxp-p);
maxp = max(maxp, p);
}

int rv = back[0];
for (int cut = 1; cutrv = max(rv, (front[cut]+back[cut+1]));
}

return rv;
}

【在 w**********4 的大作中提到】
: 总是过不了Large Judge。
: 各位大侠有更好的解法吗？
: public class Solution {
: public int maxProfit(int[] prices) {
: if (prices == null || prices.length == 0)
: return 0;
: int max =0;
: for (int i = 0;i: int value = maxProfit(prices,i);
: max = Math.max(value, max);
avatar
c*t
11 楼
再试试简化简化

【在 p*g 的大作中提到】
: int maxProfit(vector &prices) {
: int size = prices.size();
: if (size<=1)
: return 0;
:
: int* front = new int [size];
: front[0] = 0;
: int minp = prices[0];
:
: for (int i=1; i
avatar
p*g
12 楼
大侠指点一下
我琢磨了一阵， 才想到这样On的法子
最开始On2 就太慢了

【在 c********t 的大作中提到】
: 再试试简化简化
avatar
c*t
13 楼
O(n)还是O(n). 你的解法和peking2一样，已经很好了，不过还可以试试把front和back
合并用一个数组，一次循环解决。让code简化一些。也许有些吹毛求疵，但就当练练手
吧。

【在 p*g 的大作中提到】
: 大侠指点一下
: 我琢磨了一阵， 才想到这样On的法子
: 最开始On2 就太慢了
avatar
p*2
14 楼

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

int len=prices.length;
int[] dp=new int[len];
int min=prices[0];
for(int i=1;i{
min=Math.min(min, prices[i]);
dp[i]=Math.max(dp[i-1],prices[i]-min);
}
int ans=dp[len-1];
int max=prices[len-1];
dp[len-1]=0;
for(int i=len-2;i>=0;i--)
{
max=Math.max(max,prices[i]);
int tmp=Math.max(dp[i+1], max-prices[i]);
ans=Math.max(ans, dp[i]+tmp);
dp[i]=tmp;
}

return ans;
}

【在 c********t 的大作中提到】
: O(n)还是O(n). 你的解法和peking2一样，已经很好了，不过还可以试试把front和back
: 合并用一个数组，一次循环解决。让code简化一些。也许有些吹毛求疵，但就当练练手
: 吧。
avatar
r*n
15 楼
还没仔细看上面给位的代码，不过我觉得III可以化解成I的问题。
avatar
c*t
16 楼
nice.二爷总是直接上最优解，不给别人机会啊。
贴个我的
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int n = prices.length;
int buy1 = prices[0], max1 = 0;
int sell2 = prices[n - 1], max2 = 0;
int total = 0;
int[] profit = new int[n];
for (int i = 0; i < n; i++) {
buy1 = Math.min(buy1, prices[i]);
max1 = Math.max(max1, prices[i] - buy1);
profit[i] += max1;
int j = n - i - 1;
sell2 = Math.max(sell2, prices[j]);
max2 = Math.max(max2, sell2 - prices[j]);
profit[j] += max2;
}
for (int a : profit)
total = Math.max(total, a);
return total;
}

【在 p*****2 的大作中提到】
:
: back
: public int maxProfit(int[] prices) {
: if(prices==null || prices.length==0)
: return 0;
:
: int len=prices.length;
: int[] dp=new int[len];
: int min=prices[0];
: for(int i=1;i
avatar
p*2
17 楼

哈哈。我们两个的行数一样，都是18行。

【在 c********t 的大作中提到】
: nice.二爷总是直接上最优解，不给别人机会啊。
: 贴个我的
: public int maxProfit(int[] prices) {
: if (prices == null || prices.length == 0)
: return 0;
: int n = prices.length;
: int buy1 = prices[0], max1 = 0;
: int sell2 = prices[n - 1], max2 = 0;
: int total = 0;
: int[] profit = new int[n];
avatar
c*t
18 楼
:D
refer 我吧，可以帮你打下手

【在 p*****2 的大作中提到】
:
: 哈哈。我们两个的行数一样，都是18行。
avatar
w*4
19 楼
谢谢各位的代码
avatar
b*m
20 楼
二爷能不能解释一下你的DP思路呀？俺资质拙劣，不太理解呀。
avatar
T*s
21 楼
手心手背???

【在 c********t 的大作中提到】
: :D
: refer 我吧，可以帮你打下手
avatar
s*s
22 楼
感觉如果是按jordandong解释的定义的话，ans是不是应该是ans = dp1[i] + dp2[i+1]
? 因为按照题
目要求，不可能第i天既是第一次transaction的sell day，又是第二次transaction的
buy day。但是dp1[i] + dp2[i]好像包含了这种情况。
如果用ans = dp1[i] + dp2[i+1]， 最后可以再来一次 ans = Math.max(dp1[n-1],
ans);
请指正。

before

【在 j********g 的大作中提到】
: I think dp1[i] keeps the best transaction whose selling happens on or before
: day i, dp2[i] keeps the best transaction whose buying happens on or after
: day i.
: Then Max(dp1[i] + dp2[i]) returns the maximum sum of two transactions. One
: transaction finishes on or before day i, another one finishes after day i.
avatar
l*4
23 楼
非常感谢

before

【在 j********g 的大作中提到】
: I think dp1[i] keeps the best transaction whose selling happens on or before
: day i, dp2[i] keeps the best transaction whose buying happens on or after
: day i.
: Then Max(dp1[i] + dp2[i]) returns the maximum sum of two transactions. One
: transaction finishes on or before day i, another one finishes after day i.
avatar
o*d
25 楼
二爷威武

【在 p*****2 的大作中提到】
: 我刚刚练了练
: public int maxProfit(int[] prices)
: {
: if(prices==null || prices.length==0)
: return 0;
:
: int len=prices.length;
: int[] dp1=new int[len];
: int[] dp2=new int[len];
: int max=prices[len-1];
avatar
f*t
26 楼
发现最优解：
int maxProfit(vector &prices) {
int a = INT_MIN, b = INT_MIN, c = INT_MIN, d = INT_MIN;
for (size_t i=0; id = ((c != INT_MIN && c + prices[i] > d) ? c + prices[i] : d);
c = ((b != INT_MIN && b - prices[i] > c) ? b - prices[i] : c);
b = ((a != INT_MIN && a + prices[i] > b) ? a + prices[i] : b);
a = ((-prices[i] > a) ? -prices[i] : a);
}
int result = d > b ? d : b;
return result > 0 ? result : 0;
}
O(n)时间O(1)空间
给ACM大牛跪了
avatar
o*d
27 楼
shit,mark了回头看.还以为二爷的那个就最优了

;

【在 f*******t 的大作中提到】
: 发现最优解：
: int maxProfit(vector &prices) {
: int a = INT_MIN, b = INT_MIN, c = INT_MIN, d = INT_MIN;
: for (size_t i=0; i: d = ((c != INT_MIN && c + prices[i] > d) ? c + prices[i] : d);
: c = ((b != INT_MIN && b - prices[i] > c) ? b - prices[i] : c);
: b = ((a != INT_MIN && a + prices[i] > b) ? a + prices[i] : b);
: a = ((-prices[i] > a) ? -prices[i] : a);
: }
: int result = d > b ? d : b;
avatar
j*y
28 楼
太厉害了，O(1)的空间都行

;

【在 f*******t 的大作中提到】
: 发现最优解：
: int maxProfit(vector &prices) {
: int a = INT_MIN, b = INT_MIN, c = INT_MIN, d = INT_MIN;
: for (size_t i=0; i: d = ((c != INT_MIN && c + prices[i] > d) ? c + prices[i] : d);
: c = ((b != INT_MIN && b - prices[i] > c) ? b - prices[i] : c);
: b = ((a != INT_MIN && a + prices[i] > b) ? a + prices[i] : b);
: a = ((-prices[i] > a) ? -prices[i] : a);
: }
: int result = d > b ? d : b;
avatar
l*b
29 楼
没看明白人家的想法。。。自己另写了一个
int maxPIII(vector &p) {
/* observation:
* maxIII = maxI + max local drop OR maxI + another maxI
*/
int lmin = INT_MAX, lmax, ldrop, rise = 0, total = 0;
for(int i = 0; i < p.size(); ++i) {
if(p[i] < lmin) {
lmin = p[i];
lmax = p[i];
ldrop = rise;
/* reset ldrop as max of local drop and previous rise */
continue;
}
lmax = max(lmax, p[i]);
ldrop = max(ldrop, lmax - p[i]);
rise = max(rise, p[i] - lmin);
/* rise give the solution to buy sell stock I */
total = max(total, p[i] - lmin + ldrop);
}
return total;
}
avatar
b*h
30 楼
最大 m 子段和，贴一个通用做法 时间 O(n*m) 空间 O(m) 只是 m = 2
class Solution {
public:
int maxProfit(vector &prices) {
int f[3] = {0};
int g[3] = {0};
int n = prices.size() - 1;
for (int i = 0; i < n; ++i) {
int diff = prices[i+1] - prices[i];
int m = min(i+1, 2);
for (int j = m; j >= 1; --j) {
f[j] = max(f[j], g[j-1]) + diff;
g[j] = max(g[j], f[j]);
}
}
return max(g[1], g[2]);
}
};
avatar
l*b
31 楼
nice 这个思路清楚了

【在 b*********h 的大作中提到】
: 最大 m 子段和，贴一个通用做法 时间 O(n*m) 空间 O(m) 只是 m = 2
: class Solution {
: public:
: int maxProfit(vector &prices) {
: int f[3] = {0};
: int g[3] = {0};
: int n = prices.size() - 1;
: for (int i = 0; i < n; ++i) {
: int diff = prices[i+1] - prices[i];
: int m = min(i+1, 2);
avatar
j*y
32 楼
可以讲讲思路吗？ f[1], f[2], g[1], g[2] 都表示什么。 多谢.

【在 l*******b 的大作中提到】
: nice 这个思路清楚了
avatar
l*b
33 楼
g[i] 表示到当前这点为止，买卖 i次可得的最大价值。
f[i] 是从当前点之前的一个 local mininum 分开，之前做 i-1次交易，加上从这个
local min到现在可以做到的利润

【在 j*****y 的大作中提到】
: 可以讲讲思路吗？ f[1], f[2], g[1], g[2] 都表示什么。 多谢.
avatar
w*4
34 楼
总是过不了Large Judge。
各位大侠有更好的解法吗？
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int max =0;
for (int i = 0;iint value = maxProfit(prices,i);
max = Math.max(value, max);
}
return max;
}

private int maxProfit(int[] prices, int index){
int maxfront =0;
int min =0;
int maxend =0;
for (int i=0;i<=index;i++){
if (prices[i]min = i;
int diff = prices[i] - prices[min];
if (diff >maxfront){
maxfront = diff;
}
}
min = index+1;
for (int i = index+1;iif (prices[i]min = i;
int diff = prices[i] - prices[min];
if (diff >maxend){
maxend = diff;
}
}
return maxfront + maxend;
}
}
avatar
j*g
35 楼
large judge过了
class Solution {
public:
int maxProfit(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(prices.size()<=1)
return 0;

vector diff;
for(int i=0;i{
diff.push_back(prices[i+1]-prices[i]);
}

int posi =0;
int nega =0;
vector inter;
for(int j=0;j{
if(diff[j]>0){
if(nega<0){
inter.push_back(nega);
nega=0;
}
posi+=diff[j];
}
else if(diff[j]<0){
if(posi>0){
inter.push_back(posi);
posi=0;
}
nega+=diff[j];
}
}

if(nega<0){
inter.push_back(nega);
nega=0;
}
if(posi>0){
inter.push_back(posi);
posi=0;
}

int len = inter.size();
if (len==0)
return 0;

int maxb =0;
if(inter[0]>0){
if(len==1)
return inter[0];
for(int i=1;imaxb=max(cal(inter, i),maxb);
}
}else{
if(len==1)
return 0;
for(int i=0;imaxb=max(cal(inter, i),maxb);
}
}

return maxb;
}


int cal(vector &inter, int index) {
int left=0;
int right =0;
int suml =0;
int sumr=0;
for(int i =0;i{
if(suml+inter[i]>0){
suml+=inter[i];
if(suml>left)
left=suml;
}
else
suml=0;
}

for(int i =index;i{
if(sumr+inter[i]>0){
sumr+=inter[i];
if(sumr>right)
right=sumr;
}
else
sumr=0;
}

return left+right;
}
};
avatar
p*2
36 楼
我刚刚练了练
public int maxProfit(int[] prices)
{
if(prices==null || prices.length==0)
return 0;

int len=prices.length;
int[] dp1=new int[len];
int[] dp2=new int[len];
int max=prices[len-1];
int min=prices[0];

for(int i=1;i{
min=Math.min(min,prices[i]);
dp1[i]=Math.max(dp1[i-1],prices[i]-min);
}
for(int i=len-2;i>=0;i--)
{
max=Math.max(max, prices[i]);
dp2[i]=Math.max(dp2[i+1],max-prices[i]);
}

int ans=0;
for(int i=0;ians=Math.max(ans, dp1[i]+dp2[i]);
return ans;
}
avatar
c*5
37 楼
Hi,
I don't understand this part:
for(int i=0;ians=Math.max(ans, dp1[i]+dp2[i]);
Could you explain it a little more?
Thank you very much.

【在 p*****2 的大作中提到】
: 我刚刚练了练
: public int maxProfit(int[] prices)
: {
: if(prices==null || prices.length==0)
: return 0;
:
: int len=prices.length;
: int[] dp1=new int[len];
: int[] dp2=new int[len];
: int max=prices[len-1];
avatar
e*s
38 楼
2爷V5！

【在 p*****2 的大作中提到】
: 我刚刚练了练
: public int maxProfit(int[] prices)
: {
: if(prices==null || prices.length==0)
: return 0;
:
: int len=prices.length;
: int[] dp1=new int[len];
: int[] dp2=new int[len];
: int max=prices[len-1];
avatar
j*g
39 楼
I think dp1[i] keeps the best transaction whose selling happens on or before
day i, dp2[i] keeps the best transaction whose buying happens on or after
day i.
Then Max(dp1[i] + dp2[i]) returns the maximum sum of two transactions. One
transaction finishes on or before day i, another one finishes after day i.

【在 c******5 的大作中提到】
: Hi,
: I don't understand this part:
: for(int i=0;i: ans=Math.max(ans, dp1[i]+dp2[i]);
: Could you explain it a little more?
: Thank you very much.
avatar
t*n
40 楼
发个自己的吧，请指正...努力学习2爷中...
int maxProfit3(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(!prices.size())
return 0;
vector a;
vector b;
vector::iterator it;
int min = prices[0];
int profit = 0;
for(it=prices.begin(); itif(*itmin = *it;
int temp = *it - min;
if(temp > profit){
a.push_back(temp);
profit = temp;
}
else
a.push_back(profit);
}

int max = prices[prices.size()-1];
profit = 0;
for(it=prices.end()-1;it>= prices.begin();it--){
if(*it > max)
max = *it;
int temp = max - *it ;
if(temp > profit){
b.push_back(temp);
profit = temp;
}
else
b.push_back(profit);
}
reverse(b.begin(),b.end());

int maxProfit = 0;
int length = a.size();
for(int i=-1; iint temp1 = (i==-1?0:a[i]);
int temp2 = ((i==a.size()-1)?0:b[i+1]);
int temp = temp1+temp2;
if(temp > maxProfit)
maxProfit = temp;
}
return maxProfit;
}
avatar
c*t
41 楼
再试试简化简化

【在 t*********n 的大作中提到】
: 发个自己的吧，请指正...努力学习2爷中...
: int maxProfit3(vector &prices) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: if(!prices.size())
: return 0;
: vector a;
: vector b;
: vector::iterator it;
: int min = prices[0];
avatar
p*g
42 楼
int maxProfit(vector &prices) {
int size = prices.size();
if (size<=1)
return 0;

int* front = new int [size];
front[0] = 0;
int minp = prices[0];

for (int i=1; iint p = prices[i];
front[i] = max(front[i-1], p-minp);
minp = min(minp, p);
}

int* back =new int[size];
back[size-1] = 0;
int maxp = prices[size-1];

for (int i=size-2; i>=0; i--) {
int p = prices[i];
back[i] = max(back[i+1], maxp-p);
maxp = max(maxp, p);
}

int rv = back[0];
for (int cut = 1; cutrv = max(rv, (front[cut]+back[cut+1]));
}

return rv;
}

【在 w**********4 的大作中提到】
: 总是过不了Large Judge。
: 各位大侠有更好的解法吗？
: public class Solution {
: public int maxProfit(int[] prices) {
: if (prices == null || prices.length == 0)
: return 0;
: int max =0;
: for (int i = 0;i: int value = maxProfit(prices,i);
: max = Math.max(value, max);
avatar
p*g
43 楼
int maxProfit(vector &prices) {
int size = prices.size();
if (size<=1)
return 0;

int* front = new int [size];
front[0] = 0;
int minp = prices[0];

for (int i=1; iint p = prices[i];
front[i] = max(front[i-1], p-minp);
minp = min(minp, p);
}

int* back =new int[size];
back[size-1] = 0;
int maxp = prices[size-1];

for (int i=size-2; i>=0; i--) {
int p = prices[i];
back[i] = max(back[i+1], maxp-p);
maxp = max(maxp, p);
}

int rv = back[0];
for (int cut = 1; cutrv = max(rv, (front[cut]+back[cut+1]));
}

return rv;
}

【在 w**********4 的大作中提到】
: 总是过不了Large Judge。
: 各位大侠有更好的解法吗？
: public class Solution {
: public int maxProfit(int[] prices) {
: if (prices == null || prices.length == 0)
: return 0;
: int max =0;
: for (int i = 0;i: int value = maxProfit(prices,i);
: max = Math.max(value, max);
avatar
c*t
44 楼
再试试简化简化

【在 p*g 的大作中提到】
: int maxProfit(vector &prices) {
: int size = prices.size();
: if (size<=1)
: return 0;
:
: int* front = new int [size];
: front[0] = 0;
: int minp = prices[0];
:
: for (int i=1; i
avatar
p*g
45 楼
大侠指点一下
我琢磨了一阵， 才想到这样On的法子
最开始On2 就太慢了

【在 c********t 的大作中提到】
: 再试试简化简化
avatar
c*t
46 楼
O(n)还是O(n). 你的解法和peking2一样，已经很好了，不过还可以试试把front和back
合并用一个数组，一次循环解决。让code简化一些。也许有些吹毛求疵，但就当练练手
吧。

【在 p*g 的大作中提到】
: 大侠指点一下
: 我琢磨了一阵， 才想到这样On的法子
: 最开始On2 就太慢了
avatar
p*2
47 楼

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

int len=prices.length;
int[] dp=new int[len];
int min=prices[0];
for(int i=1;i{
min=Math.min(min, prices[i]);
dp[i]=Math.max(dp[i-1],prices[i]-min);
}
int ans=dp[len-1];
int max=prices[len-1];
dp[len-1]=0;
for(int i=len-2;i>=0;i--)
{
max=Math.max(max,prices[i]);
int tmp=Math.max(dp[i+1], max-prices[i]);
ans=Math.max(ans, dp[i]+tmp);
dp[i]=tmp;
}

return ans;
}

【在 c********t 的大作中提到】
: O(n)还是O(n). 你的解法和peking2一样，已经很好了，不过还可以试试把front和back
: 合并用一个数组，一次循环解决。让code简化一些。也许有些吹毛求疵，但就当练练手
: 吧。
avatar
r*n
48 楼
还没仔细看上面给位的代码，不过我觉得III可以化解成I的问题。
avatar
c*t
49 楼
nice.二爷总是直接上最优解，不给别人机会啊。
贴个我的
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int n = prices.length;
int buy1 = prices[0], max1 = 0;
int sell2 = prices[n - 1], max2 = 0;
int total = 0;
int[] profit = new int[n];
for (int i = 0; i < n; i++) {
buy1 = Math.min(buy1, prices[i]);
max1 = Math.max(max1, prices[i] - buy1);
profit[i] += max1;
int j = n - i - 1;
sell2 = Math.max(sell2, prices[j]);
max2 = Math.max(max2, sell2 - prices[j]);
profit[j] += max2;
}
for (int a : profit)
total = Math.max(total, a);
return total;
}

【在 p*****2 的大作中提到】
:
: back
: public int maxProfit(int[] prices) {
: if(prices==null || prices.length==0)
: return 0;
:
: int len=prices.length;
: int[] dp=new int[len];
: int min=prices[0];
: for(int i=1;i
avatar
p*2
50 楼

哈哈。我们两个的行数一样，都是18行。

【在 c********t 的大作中提到】
: nice.二爷总是直接上最优解，不给别人机会啊。
: 贴个我的
: public int maxProfit(int[] prices) {
: if (prices == null || prices.length == 0)
: return 0;
: int n = prices.length;
: int buy1 = prices[0], max1 = 0;
: int sell2 = prices[n - 1], max2 = 0;
: int total = 0;
: int[] profit = new int[n];
avatar
c*t
51 楼
:D
refer 我吧，可以帮你打下手

【在 p*****2 的大作中提到】
:
: 哈哈。我们两个的行数一样，都是18行。
avatar
w*4
52 楼
谢谢各位的代码
avatar
b*m
53 楼
二爷能不能解释一下你的DP思路呀？俺资质拙劣，不太理解呀。
avatar
T*s
54 楼
手心手背???

【在 c********t 的大作中提到】
: :D
: refer 我吧，可以帮你打下手
avatar
s*s
55 楼
感觉如果是按jordandong解释的定义的话，ans是不是应该是ans = dp1[i] + dp2[i+1]
? 因为按照题
目要求，不可能第i天既是第一次transaction的sell day，又是第二次transaction的
buy day。但是dp1[i] + dp2[i]好像包含了这种情况。
如果用ans = dp1[i] + dp2[i+1]， 最后可以再来一次 ans = Math.max(dp1[n-1],
ans);
请指正。

before

【在 j********g 的大作中提到】
: I think dp1[i] keeps the best transaction whose selling happens on or before
: day i, dp2[i] keeps the best transaction whose buying happens on or after
: day i.
: Then Max(dp1[i] + dp2[i]) returns the maximum sum of two transactions. One
: transaction finishes on or before day i, another one finishes after day i.
avatar
l*4
56 楼
非常感谢

before

【在 j********g 的大作中提到】
: I think dp1[i] keeps the best transaction whose selling happens on or before
: day i, dp2[i] keeps the best transaction whose buying happens on or after
: day i.
: Then Max(dp1[i] + dp2[i]) returns the maximum sum of two transactions. One
: transaction finishes on or before day i, another one finishes after day i.
avatar
o*d
58 楼
二爷威武

【在 p*****2 的大作中提到】
: 我刚刚练了练
: public int maxProfit(int[] prices)
: {
: if(prices==null || prices.length==0)
: return 0;
:
: int len=prices.length;
: int[] dp1=new int[len];
: int[] dp2=new int[len];
: int max=prices[len-1];
avatar
f*t
59 楼
发现最优解：
int maxProfit(vector &prices) {
int a = INT_MIN, b = INT_MIN, c = INT_MIN, d = INT_MIN;
for (size_t i=0; id = ((c != INT_MIN && c + prices[i] > d) ? c + prices[i] : d);
c = ((b != INT_MIN && b - prices[i] > c) ? b - prices[i] : c);
b = ((a != INT_MIN && a + prices[i] > b) ? a + prices[i] : b);
a = ((-prices[i] > a) ? -prices[i] : a);
}
int result = d > b ? d : b;
return result > 0 ? result : 0;
}
O(n)时间O(1)空间
给ACM大牛跪了
avatar
o*d
60 楼
shit,mark了回头看.还以为二爷的那个就最优了

;

【在 f*******t 的大作中提到】
: 发现最优解：
: int maxProfit(vector &prices) {
: int a = INT_MIN, b = INT_MIN, c = INT_MIN, d = INT_MIN;
: for (size_t i=0; i: d = ((c != INT_MIN && c + prices[i] > d) ? c + prices[i] : d);
: c = ((b != INT_MIN && b - prices[i] > c) ? b - prices[i] : c);
: b = ((a != INT_MIN && a + prices[i] > b) ? a + prices[i] : b);
: a = ((-prices[i] > a) ? -prices[i] : a);
: }
: int result = d > b ? d : b;
avatar
j*y
61 楼
太厉害了，O(1)的空间都行

;

【在 f*******t 的大作中提到】
: 发现最优解：
: int maxProfit(vector &prices) {
: int a = INT_MIN, b = INT_MIN, c = INT_MIN, d = INT_MIN;
: for (size_t i=0; i: d = ((c != INT_MIN && c + prices[i] > d) ? c + prices[i] : d);
: c = ((b != INT_MIN && b - prices[i] > c) ? b - prices[i] : c);
: b = ((a != INT_MIN && a + prices[i] > b) ? a + prices[i] : b);
: a = ((-prices[i] > a) ? -prices[i] : a);
: }
: int result = d > b ? d : b;
avatar
l*b
62 楼
没看明白人家的想法。。。自己另写了一个
int maxPIII(vector &p) {
/* observation:
* maxIII = maxI + max local drop OR maxI + another maxI
*/
int lmin = INT_MAX, lmax, ldrop, rise = 0, total = 0;
for(int i = 0; i < p.size(); ++i) {
if(p[i] < lmin) {
lmin = p[i];
lmax = p[i];
ldrop = rise;
/* reset ldrop as max of local drop and previous rise */
continue;
}
lmax = max(lmax, p[i]);
ldrop = max(ldrop, lmax - p[i]);
rise = max(rise, p[i] - lmin);
/* rise give the solution to buy sell stock I */
total = max(total, p[i] - lmin + ldrop);
}
return total;
}
avatar
b*h
63 楼
最大 m 子段和，贴一个通用做法 时间 O(n*m) 空间 O(m) 只是 m = 2
class Solution {
public:
int maxProfit(vector &prices) {
int f[3] = {0};
int g[3] = {0};
int n = prices.size() - 1;
for (int i = 0; i < n; ++i) {
int diff = prices[i+1] - prices[i];
int m = min(i+1, 2);
for (int j = m; j >= 1; --j) {
f[j] = max(f[j], g[j-1]) + diff;
g[j] = max(g[j], f[j]);
}
}
return max(g[1], g[2]);
}
};
avatar
l*b
64 楼
nice 这个思路清楚了

【在 b*********h 的大作中提到】
: 最大 m 子段和，贴一个通用做法 时间 O(n*m) 空间 O(m) 只是 m = 2
: class Solution {
: public:
: int maxProfit(vector &prices) {
: int f[3] = {0};
: int g[3] = {0};
: int n = prices.size() - 1;
: for (int i = 0; i < n; ++i) {
: int diff = prices[i+1] - prices[i];
: int m = min(i+1, 2);
avatar
j*y
65 楼
可以讲讲思路吗？ f[1], f[2], g[1], g[2] 都表示什么。 多谢.

【在 l*******b 的大作中提到】
: nice 这个思路清楚了
avatar
l*b
66 楼
g[i] 表示到当前这点为止，买卖 i次可得的最大价值。
f[i] 是从当前点之前的一个 local mininum 分开，之前做 i-1次交易，加上从这个
local min到现在可以做到的利润

【在 j*****y 的大作中提到】
: 可以讲讲思路吗？ f[1], f[2], g[1], g[2] 都表示什么。 多谢.
avatar
J*o
67 楼
Mark
相关阅读
高考完，大学专业求建议。G offer 供参考non profit的研究机构，能不能sponsor non-cap H1b?老是出现这样的情况，让职场新人何以应对？求帮助。讨论：关于要求加薪的问题有个猎头公司人跟我要ssn后四位，骗子？既然没出路又是苦逼专业为啥犹豫不转马工呢？degree八月份才award，工作7月1日开始，单位不给pay，包子求助我们组最近招CS专业的QA，有兴趣的短信给我求telecommute统计Part time工作机会大家推荐个改简历的英文网站吧g家的工资base每年一般涨多少有没地方既有油工又有码工机会真心求教,向成功转行CS的前辈们EAD没收到怎么办?有三月份申请OPT还没下来的吗？USPS把EAD给寄丢了我也来说一下油工有感兴趣的吗? (.NET Developer)关于背景调查
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。