输入数组为:
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)进行优化。我无法想象如何避免嵌套...任何指向正确方向的指针都将不胜感激。