資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++程式：查詢單次反轉後最大相鄰絕對值之和
假設我們有一個名為nums的數字列表，我們最多可以反轉列表中的任何子列表一次。執行此操作後，我們必須找到以下最大可能值：
$\displaystyle\sum\limits_{i=0}^{n-2}| nums[i+1]-[nums[i]|$
因此，如果輸入類似於nums = [2, 4, 6]，則輸出將為6，因為當我們反轉[4, 6]時，我們將得到列表[2, 6, 4]，而值|2 − 6| + |6 − 4| = 6
為了解決這個問題，我們將遵循以下步驟：
如果nums的大小<= 1，則：
返回0
ans := 0
n := nums的大小
對於初始化i := 1，當i < n時，更新（i增加1），執行：
ans := ans + |nums[i] − nums[i − 1]|
orig := ans
對於初始化i := 1，當i < n − 1時，更新（i增加1），執行：
ans := ans和orig − |(nums[i] − nums[i + 1]| + |nums[0] − nums[i + 1]| 的最大值
ans := ans和orig − |(nums[i] − nums[i − 1]| + |nums[n − 1] − nums[i − 1]| 的最大值
pp := −|nums[1] − nums[0]|
pm := −|nums[1] − nums[0]|
mp := −|nums[1] − nums[0]|
mm := −|nums[1] − nums[0]|
對於初始化j := 2，當j < n − 1時，更新（j增加1），執行：
jerror := |nums[j + 1] − nums[j]|
ans := ans和(orig + pp − jerror − nums[j] − nums[j + 1])的最大值
ans := ans和(orig + pm − jerror − nums[j] + nums[j + 1])的最大值
ans := ans和(orig + mp − jerror + nums[j] − nums[j + 1])的最大值
ans := ans和(orig + mm − jerror + nums[j] + nums[j + 1])的最大值
pp := pp和−|nums[j] − nums[j − 1]| 的最大值
pm := pm和−|nums[j] − nums[j − 1]| 的最大值
mp := mp和−|nums[j] − nums[j − 1]| 的最大值
mm := mm和−|nums[j] − nums[j − 1]| 的最大值
返回ans
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums) {
if (nums.size() <= 1)
return 0;
int ans = 0;
int n = nums.size();
for (int i = 1; i < n; i++) {
ans += abs(nums[i] − nums[i − 1]);
}
int orig = ans;
for (int i = 1; i < n − 1; i++) {
ans = max(ans, orig − abs(nums[i] − nums[i + 1]) +
abs(nums[0] − nums[i + 1]));
ans = max(ans, orig − abs(nums[i] − nums[i − 1]) + abs(nums[n
− 1] − nums[i − 1]));
}
int pp = −abs(nums[1] − nums[0]) + nums[0] + nums[1];
int pm = −abs(nums[1] − nums[0]) + nums[0] − nums[1];
int mp = −abs(nums[1] − nums[0]) − nums[0] + nums[1];
int mm = −abs(nums[1] − nums[0]) − nums[0] − nums[1];
for (int j = 2; j < n − 1; j++) {
int jerror = abs(nums[j + 1] − nums[j]);
ans = max(ans, orig + pp − jerror − nums[j] − nums[j + 1]);
ans = max(ans, orig + pm − jerror − nums[j] + nums[j + 1]);
ans = max(ans, orig + mp − jerror + nums[j] − nums[j + 1]);
ans = max(ans, orig + mm − jerror + nums[j] + nums[j + 1]);
pp = max(pp, −abs(nums[j] − nums[j − 1]) + nums[j − 1] +
nums[j]);
pm = max(pm, −abs(nums[j] − nums[j − 1]) + nums[j − 1] −
nums[j]);
mp = max(mp, −abs(nums[j] − nums[j − 1]) − nums[j − 1] +
nums[j]);
mm = max(mm, −abs(nums[j] − nums[j − 1]) − nums[j − 1] −
nums[j]);
}
return ans;
}
int main(){
vector<int> v = {2, 4, 6};
cout << solve(v);
}輸入
{2, 4, 6}輸出
6
瀏覽量：119
