b*******g
发帖数: 36 | 1 题目如下，可以直接google "hackrank stock maximize",测试自己代码是否正确：
https://www.hackerrank.com/challenges/stockmax
Your algorithms have become so good at predicting the market that you now
know what the share price of Wooden Orange Toothpicks Inc. (WOT) will be for
the next N days.
Each day, you can either buy one share of WOT, sell any number of shares of
WOT that you own, or not make any transaction at all. What is the maximum
profit you can obtain with an optimum trading strategy?
Input
The first line contains the number of test cases T. T test cases follow:
The first line of each test case contains a number N. The next line contains
N integers, denoting the predicted price of WOT shares for the next N days.
Output
Output T lines, containing the maximum profit which can be obtained for the
corresponding test case.
Constraints
1 <= T <= 10
1 <= N <= 50000
All share prices are between 1 and 100000
Sample Input
3
3
5 3 2
3
1 2 100
4
1 3 1 2
Sample Output
0
197
3
我按照网上方法先右遍历，再左遍历，java代码如下，但不能pass tests； 求正确
java 代码
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to
STDOUT. Your class should be named Solution. */
Scanner sc = new Scanner(System.in);
int numOfTestCase = sc.nextInt();
for (int i = 0; i < numOfTestCase; i++) {
int n = sc.nextInt();
int[] stockPrice = new int[n];
for (int j = 0; j < n; j++) {
stockPrice[j] = sc.nextInt();
}
int max = 0;
int[] leftMax = new int[n];
for (int j = n - 1; j >= 0; j--) {
if(stockPrice[j] > max)
max = stockPrice[i];
leftMax[j] = max;
}
long profit = 0;
for(int k=0;k
if(leftMax[k] > stockPrice[k])
profit += leftMax[k]-stockPrice[k];
}
System.out.println(profit);
}
sc.close();
}
} |
b*******g
发帖数: 36 | 2 个人觉得思路似乎是对的
但是没明白为何跑出错误的结果 |
n**e
发帖数: 116 | |
q**y
发帖数: 129 | 4 应该是leftMax[k+1] 和 stockPrice[k]相减吧。
我的accepted的c++ code （去除了IO）.
long maxStockProfit (vector stockPrices) {
int maxSellPrice = 0;
long maxProfit = 0;
for (int dayIdx= stockPrices.size()-2; dayIdx>=0; dayIdx--) {
maxSellPrice = max(maxSellPrice, stockPrices[dayIdx+1]);
maxProfit += (maxSellPrice - stockPrices[dayIdx]) > 0? (maxSellPrice
- stockPrices[dayIdx]) : 0;
}
return maxProfit;
} |
b*******g
发帖数: 36 | 5 谢谢
的。
ii
【在 n**e 的大作中提到】
: 这个跟leetcode Best的 Time to Buy and Sell Stock II是一样的。扫一遍就可以的。
: https://leetcode.com/discuss/questions/oj/best-time-to-buy-and-sell-stock-ii
|
b*******g
发帖数: 36 | 6 是的， 谢谢
maxSellPrice
【在 q**y 的大作中提到】
: 应该是leftMax[k+1] 和 stockPrice[k]相减吧。
: 我的accepted的c++ code （去除了IO）.
: long maxStockProfit (vector stockPrices) {
: int maxSellPrice = 0;
: long maxProfit = 0;
:
: for (int dayIdx= stockPrices.size()-2; dayIdx>=0; dayIdx--) {
: maxSellPrice = max(maxSellPrice, stockPrices[dayIdx+1]);
: maxProfit += (maxSellPrice - stockPrices[dayIdx]) > 0? (maxSellPrice
: - stockPrices[dayIdx]) : 0;
|
w********g
发帖数: 8 | 7 max = stockPrice[i];
是不是这句话有问题啊 |
