資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告