数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中反转子数组以最大化数组值
假设我们有一个名为nums的整数数组。此数组的值定义为所有i（范围为0到n-1）的|nums[i]-nums[i+1]|之和，其中n是数组的大小。我们可以选择给定数组的任何子数组并将其反转。我们只能执行此操作一次。然后我们必须找到最终数组的最大可能值。
因此，如果输入类似于[1,5,4,2,3]，则输出将为10。
为了解决这个问题，我们将遵循以下步骤：
ret := 0, extra := 0
n := nums的大小
minVal := inf, maxVal := -inf
for i := 0 to n - 1 −
a := nums[i], b := nums[i + 1]
ret := ret + |b - a|
extra := max(extra, |(nums[0] - b) - |a - b||)
extra := max(extra, |(nums[n - 1] - a) - |a - b||)
maxVal := max(maxVal, min(a, b))
minVal := min(minVal, max(a, b))
return ret + max(extra, (maxVal - minVal) * 2)
让我们看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxValueAfterReverse(vector<int>& nums) {
int ret = 0;
int extra = 0;
int n = nums.size();
int minVal = INT_MAX;
int maxVal = INT_MIN;
for(int i = 0; i < n - 1; i++){
int a = nums[i];
int b = nums[i + 1];
ret += abs(b - a);
extra = max(extra, abs(nums[0] - b) - abs(a - b));
extra = max(extra, abs(nums[n - 1] - a) - abs(a - b));
maxVal = max(maxVal, min(a, b));
minVal = min(minVal, max(a, b));
}
return ret + max(extra, (maxVal - minVal) * 2);
}
};
main(){
Solution ob;
vector<int> v = {1,5,4,2,3};
cout << (ob.maxValueAfterReverse(v));
}输入
{1,5,4,2,3}输出
10
更新于：2020年6月8日
432 次查看
广告