基础问题：给定一个整数数组选出 2 个数，使他们的总和最大。

• 暴力算法：O（n^2）,略。
• 时间复杂度为O（n）的解法：考虑数组中的两个数nums[i], nums[j], i < j且∈[0, n),从前往后枚举第二个数，对于每个nums[j]来说，只关心它前面最大的那个数字， 因为只有前面最大的数和nums[j] 相加才可能产生最大的结果。因此在枚举j的过程中，维护j之前的最大的数即可。

    int n = nums.size();
    int maxNi = nums[0];
    int ansTwo = nums[0] + nums[1];
    for(int j = 1; j < n; ++j){//j = 1开始，枚举第二个数
        maxNi = max(maxNi, nums[j-1]); 
        ansTwo = max(ansTwo, maxNi + nums[j]);
    }
    cout << ansTwo << endl; 

问题升维：给定一个整数数组选出 3 个数，使他们的总和最大。

• 在上述基础问题的基础上，由于2个数有O（n）的解法，因此对于3个数的情况，显然可以在枚举j之后，再从 [ j + 1,n) 中找一个最大的数，但是这个做法时间复杂度是O（N^2）

• 仔细分析这个问题的本质：实际上可以使用同样的思想来处理3个数的问题，关键思想：对于每个j更新完后，ansTwo里就是从[0,j] 中最大的两个数的和。那么对于第三个下标j+1，只需要关心它前面最大的ansTwo，因为只有前面最大的两数之和与nums[j+1] 相加才可能产生最大的结果。因此在枚举j+1的过程中，维护之前的ansTwo即可。

int n = nums.size();
    int maxNi = nums[0];
    int ansTwo = nums[0] + nums[1];
    int ansThree = nums[0] + nums[1] + nums[2];
    for(int j = 2; j < n; ++j){//这里从j = 2开始相当于枚举第三个数
        maxNi = max(maxNi, nums[j-2]); 
        ansTwo = max(ansTwo, maxNi + nums[j-1]);
        ansThree = max(ansThree, ansTwo + nums[j]); 
    }
    cout << ansThree << endl;

总结与讨论

• 可以将其理解为一种特殊的动态规划；
• 对于类似数组中顺序的数据的最大/小的和/差，可以先维护前面的结果，枚举后面的数据即可。这个思想的用途非常广泛。

例题运用

今日LC每日一题：2016. 增量元素之间的最大差值

给你一个下标从 0 开始的整数数组 nums ，该数组的大小为 n ，请你计算 nums[j] - nums[i] 能求得的 最大差值 ，其中 0 <= i < j < n 且 nums[i] < nums[j] 。

返回 最大差值 。如果不存在满足要求的 i 和 j ，返回 -1 。

class Solution {
	//枚举第j个数字，维护j前面最小的数min，最大差值只可能由nums[j] - min产生
    public int maximumDifference(int[] nums) {
		int min = nums[0];
        int ans = -1;
        int n = nums.length;
        for (int j = 1; j < n; j++) {
        	min = Math.min(min, nums[j-1]);
            if (nums[j] > min) {
                ans = Math.max(ans, nums[j] - min);
            }
        }
        return ans;
    }
}