📃 题目描述

题目链接：没有，我自己做笔试的时候遇到的问题

一个无序数组，求 a[i] +a[j] +i - j 的最大值，要求 i < j

🔔 解题思路

正确思路是把 a[i]+a[j]+i-j 拆成 (a[i]+i)+(a[j]-j)。

• 直接遍历一遍数组，找到每个 j 左边的最大 a[i] + i，这样对于 j 来说，就是最大的 a[i] + i + a[j] - j

时间复杂度：O(n)

public class Main3 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] nums = new long[n];
        for (int i = 0; i < n; i ++) {
            nums[i] = sc.nextLong();
        }
        System.out.println(func(n, nums));

    }

    private static long func(int n, long[] nums) {
        long max = 0;

        // nums[j] 左边的(不包括 nums[j] 本身) nums[i] + i 的最大值
        long[] maxLeftNum = new long[n];
        maxLeftNum[1] = nums[0];

        for (int i = 2; i < n; j ++) {
            if (nums[i - 1] + i - 1) > maxLeftNum[i - 1]) {
                maxLeftNum[i] = nums[i - 1] + i - 1;
            }
            else {
                maxLeftNum[i] = maxLeftNum[i - 1];
            }
        }

        for (int j = 1; j < n; j ++) {
            long sum = nums[j] - j + maxLeftNum[j];
            max = Math.max(sum, max);
        }

        return max;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：