資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律在 C++ 中選擇最大和 M 個元素，使得連續重複不超過 K
在這個問題中，我們給定一個數組 arr[] 和兩個整數 M 和 K。我們的任務是使用給定陣列的元素建立一個數組。新陣列的大小應為 M，並且任何大小大於 K 的子陣列都不能所有元素都相同。我們必須列印建立的陣列可能的最大和。
讓我們舉個例子來理解這個問題
輸入 − arr[] = {1, 2, 4, 5, 7 }, M = 5, K = 2
說明 − 建立滿足條件的陣列 {7, 7, 5, 7, 7}。這裡，沒有大小超過 2 的子陣列的所有元素都相同。
為了解決這個問題，我們需要使用具有最大值的元素建立陣列。但我們不能使用最大元素超過 k 次，因此 k 次之後，我們將不得不使用陣列的第二大元素。在陣列中每隔 k 個最大值插入一個第二大值，並建立一個長度為 M 的陣列。最終輸出將是此陣列中所有元素的總和。
示例
程式演示了我們解決方案的實現，
#include <iostream>
using namespace std;
long int arraySum(int arr[], int n, int m, int k){
int max1 = arr[0], max2 = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max1) {
max2 = max1;
max1 = arr[i];
}
else if (arr[i] > max2)
max2 = arr[i];
}
int max2count = m / (k + 1);
long int sum = max2count * max2 + (m - max2count) * max1;
return sum;
}
int main() {
int arr[] = { 1, 3, 6, 7, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int m = 9, k = 2;
cout<<"The maximum sum of array created from the given array such that no subarray of size greater than "<<k<<" will have same elements is ";
cout<<arraySum(arr, n, m, k);
return 0;
}輸出
The maximum sum of array created from the given array such that no subarray of size greater than 2 will have same elements is 60
更新於: 2020-04-17
223 次瀏覽
廣告