问题

Question

已知一个数组a[1000000]; 有 0<= i < j <= 1000000;
找到满足条件的 i, j  使 a[i] - a[j] 最大

Answer 1

楼主这2题是作业？
感觉是刚才那个题目的扩充
这个题的原理是
b[i] = a[i] - a[i+1];
a[i] - a[j] = a[i] - a[i+1] + a[i+1] - a[i+2] +.... + a[j-1] - a[j];
            = b[i] + b[i+1] +.....+ b[j-1]public class GetValuesOfSubArray {
public static int getMaxDifOfArray(int[] values) {
int[] newArr = new int[values.length - 1];
for (int i = 0; i < newArr.length; i++) {
newArr[i] = values[i] - values[i + 1];
}
return getMaxSumOfSubArray(newArr);
}
public static int getMaxSumOfSubArray(int[] values) {
int nStart = values[values.length - 1];
int nAll = nStart;
for (int i = values.length - 2; i >= 0; i--) {
nStart = Math.max(values[i], nStart + values[i]);
nAll = Math.max(nStart, nAll);
}
return nAll;
}
}