面试算法题精讲：求数组两组数差值和的最大值
题目描述
给定一个数组 nums，求 (nums[j]-nums[i])+(nums[h]-nums[k]) 的最大值，其中 0<i<j<k<h<nums.size()。
解法：前后缀分解
代码：
int maxExpression(const vector<int> &nums)
{int n = nums.size();// 如果数组长度不足4个元素，返回 -1 表示无解if (n < 4)return -1;// 用来存储从左往右的最大 nums[j] - nums[i]vector<int> left_max(n, 0);int min_i = nums[0];for (int i = 1; i < n; i++){left_max[i] = max(left_max[i - 1], nums[i] - min_i);min_i = min(min_i, nums[i]); // 维护最小的 nums[i]}// 用来存储从右往左的最大 nums[h] - nums[k]vector<int> right_max(n, 0);int max_h = nums[n - 1];for (int i = n - 2; i >= 0; i--){right_max[i] = max(right_max[i + 1], max_h - nums[i]);max_h = max(max_h, nums[i]); // 维护最大的 nums[h]}// 最终结果是 left_max 和 right_max 的最大和int result = INT_MIN;for (int i = 1; i < n - 2; i++){ // i 需要小于 n-2，因为后面还有 k 和 hresult = max(result, left_max[i] + right_max[i + 1]);}return result;
}
)
