输入数组是:
A[0] = 23171
A[1] = 21015
A[2] = 21123
A[3] = 21366
A[4] = 21013
A[5] = 21367
任务是找到最大利润。例如 A[3] - A[2] = 243 我的代码是:
class Solution {
int profit = 0;
public int solution(int[] A) {
for (int i = 0;i < A.length; i++){
for (int j = i + 1; j < A.length; j++){
if(A[j] - A[i] > profit)
profit = A[j] - A[i];
}
}
return profit;
}
}
结果应该是 365,但它会在更大的输入上爆炸。 此代码的时间复杂度为 O(N2),但可以用 O(N) 来处理。我真的看不出如何避免在这里嵌套...感谢任何指向正确方向的指示。
最佳答案
您只需要从数组中获取最大值和最小值并将它们相减,因此在 O(N) 迭代中,获取最小值和最大值。
class Solution {
public int solution(int[] A) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0;i < A.length; i++){
if(A[i] > max) max = A[i];
if(A[i] < min) min = A[i];
}
return max - min;
}
}
关于java - 最大单次卖出利润算法的最优解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19959084/