给定一个整数数组，求a[i]+a[j]+i-j的最大值—头条笔试题

问题

给定一个整数数组，求数组中两个数关于公式 a[i]+a[j]+i-j 的最大值，即找两个数，这两个数相加并减去两个数之间的下标距离，求得最大值。 例如： input: 3 1 2 3 output: 4(选择的两个数是2和3)

扩展：这个题目可以有变形，例如求一个数组中两数和的最大值，两数差的最大值，或两数和差和某些变量构成的公式的最大值。

思路

（1）基本思路：暴力搜索，遍历每一个数对，进行判断，复杂度为O(n^2) （2）优化思路：对于遍历到的数，寻找其左边的最大值进行求和，因为只有左边的最大值与其相加才能构成更大值。所以每次维护一个左边的最大值，遍历一遍即可。时间复杂度O(n),空间复杂度O(1)

import java.util.*; public class TT { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int maxScore = 0; int tmp = 0; int[] score = new int[n]; for(int i = 0; i < n; i++){ score[i] = in.nextInt(); } // 暴力搜索法 // for(int i = 0; i < n -1; i++){ // for(int j = i + 1; j < n; j++){ // tmp = score[i] + score[j] + i - j; // if(tmp > maxScore){ // maxScore = tmp; // } // } // } // int[] maxLeft = new int[n]; int maxLeftScore = score[0]; // 维护一个左边最大值的数组，其实并不需要，因为每次只会用到一个最大值 // 所以只用维护一个最大值即可 // for(int i = 0; i < n; i++){ // tmp = score[i] + i; // if(tmp > maxLeftScore){ // maxLeft[i] = tmp; // maxLeftScore = tmp; // }else{ // maxLeft[i] = maxLeftScore; // } // } // System.out.println(maxLeft.toString()); for(int i = 1; i < n; i++){ tmp = maxLeftScore + score[i] - i; if(tmp > maxScore){ maxScore = tmp; } if(score[i] + i > maxLeftScore){ maxLeftScore = score[i] + i; } } System.out.println(maxScore); } }