给定一个N个数的数组，我们需要最大化所选数的和。在每个步骤中，您都需要选择一个数字a 我 ，删除其中一个实例，并删除所有实例 A. 我 -1 和 A. 我 +1 （如果存在）在数组中。重复这些步骤，直到数组变空。问题是最大化所选数字的总和。
null
注： 我们必须删除所有出现的 我 +1和A 我 -1个元素，如果它们存在于数组中而不是 i+1 还有 i-1 .
例如：
Input : a[] = {1, 2, 3} Output : 4Explanation: At first step we select 1, so 1 and 2 are deleted from the sequence leaving us with 3. Then we select 3 from the sequence and delete it.So the sum of selected numbers is 1+3 = 4. Input : a[] = {1, 2, 2, 2, 3, 4}Output : 10 Explanation : Select one of the 2's from the array, so 2, 2-1, 2+1 will be deleted and we are left with {2, 2, 4}, since 1 and 3 are deleted. Select 2 in next two steps, and then select 4 in the last step.We get a sum of 2+2+2+4=10 which is the maximum possible.
我们的目标是最大化所选数字的总和。其思想是预先计算数组a[]中所有数字x的出现次数。
方法：
- 计算数组中的最大值。
- 创建一个最大大小的数组，并存储其中每个元素的引用。
- 因为我们想要最大化我们的答案，我们将开始从最大值迭代到0。
- 如果 th 元素大于0，然后将其添加到我们的答案中，以减少i-1的出现 th 元素增加1，也减少了i的发生 th 1，因为我们已经把它添加到了我们的答案中。
- 我们不必减少i+1的发生 th 元素，因为我们已经从末尾开始了，所以i+1 th 已经处理过了。
- 可能会多次出现i th 这就是为什么我还没有减少i，保持在同一个元素上。
以下是上述理念的实施情况：
C++
// CPP program to Maximize the sum of selected // numbers by deleting three consecutive numbers. #include <bits/stdc++.h> using namespace std; // function to maximize the sum of selected numbers int maximizeSum( int arr[], int n) { // Largest element in the array int mx = -1; for ( int i = 0; i < n; i++) { mx = max(mx, arr[i]); } // An array to count the occurrence of each element int freq[mx + 1]; memset (freq, 0, sizeof (freq)); for ( int i = 0; i < n; i++) { freq[arr[i]]++; } // ans to store the result int ans = 0, i=mx; // Using the above mentioned approach while (i>0){ // if occurrence is greater than 0 if (freq[i] > 0){ // add it to ans ans += i; // decrease i-1th element by 1 freq[i-1]--; // decrease ith element by 1 freq[i]--; } else { // decrease i i--; } } return ans; } // Driver code int main() { int a[] = {1, 2, 3}; int n = sizeof (a) / sizeof (a[0]); cout << maximizeSum(a, n); return 0; } |
JAVA
// Java implementation of the approach import java.util.*; import java.math.*; class GFG { // Function to maximise the sum of selected numbers //by deleting occurrences of Ai-1 and Ai+1 public static int getMaximumSum ( int arr[]) { // Number of elements in the array int n = arr.length; // Largest element in the array int max = - 1 ; for ( int i = 0 ; i < n; i++) { max = Math.max(max, arr[i]); } // An array to count the occurrence of each element int []freq = new int [max + 1 ]; for ( int i = 0 ; i < n; i++) { freq[arr[i]]++; } // ans to store the result int ans = 0 , i=max; // Using the above mentioned approach while (i> 0 ){ // if occurence is greater than 0 if (freq[i] > 0 ){ // add it to ans ans += i; // decrease i-1th element by 1 freq[i- 1 ]--; // decrease ith element by 1 freq[i]--; } else { // decrease i i--; } } return ans; } // Driver code public static void main(String[] args) { int []a = { 1 , 2 , 3 }; System.out.println(getMaximumSum(a)); } } |
Python3
# Python3 program to Maximize the sum of selected # numbers by deleting three consecutive numbers. # function to maximize the sum of # selected numbers def maximizeSum(a, n) : # maximum in the sequence maximum = max (a) # stores the occurrences of the numbers ans = dict .fromkeys( range ( 0 , n + 1 ), 0 ) # marks the occurrence of every # number in the sequence for i in range (n) : ans[a[i]] + = 1 # ans to store the result result = 0 i = maximum # Using the above mentioned approach while i > 0 : # if occurrence is greater than 0 if ans[i] > 0 : # add it to ans result + = i; # decrease i-1th element by 1 ans[i - 1 ] - = 1 ; # decrease ith element by 1 ans[i] - = 1 ; else : # decrease i i - = 1 ; return result; # Driver code if __name__ = = "__main__" : a = [ 1 , 2 , 3 ] n = len (a) print (maximizeSum(a, n)) # This code is contributed by Ryuga |
C#
// C# implementation of the approach using System; using System.Linq; class GFG { // Function to maximise the sum of selected numbers //by deleting occurrences of Ai-1 and Ai+1 static int getMaximumSum( int []arr) { // Number of elements in the array int n = arr.Length; // Largest element in the array int max = arr.Max(); // An array to count the occurrence of each element int []freq = new int [max + 1]; for ( int j = 0; j < n; j++) { freq[arr[j]]++; } // ans to store the result int ans = 0, i=max; // Using the above mentioned approach while (i>0){ // if occurence is greater than 0 if (freq[i] > 0){ // add it to ans ans += i; // decrease i-1th element by 1 freq[i-1]--; // decrease ith element by 1 freq[i]--; } else { // decrease i i--; } } return ans; } // Driver code public static void Main( string [] args) { int []a = {1, 2, 3}; Console.Write(getMaximumSum(a)); } } // This code is contributed by rock_cool |
Javascript
<script> // Javascript implementation of the approach // Function to maximise the sum of selected numbers //by deleting occurrences of Ai-1 and Ai+1 function getMaximumSum(arr) { // Number of elements in the array let n = arr.length; // Largest element in the array let max = Number.MIN_VALUE; for (let i = 0; i < n; i++) { max = Math.max(max, arr[i]); } // An array to count the occurrence of each element let freq = new Array(max + 1); freq.fill(0); for (let j = 0; j < n; j++) { freq[arr[j]]++; } // ans to store the result let ans = 0, i=max; // Using the above mentioned approach while (i>0){ // if occurence is greater than 0 if (freq[i] > 0){ // add it to ans ans += i; // decrease i-1th element by 1 freq[i-1]--; // decrease ith element by 1 freq[i]--; } else { // decrease i i--; } } return ans; } let a = [1, 2, 3]; document.write(getMaximumSum(a)); // This code is contributed by suresh07. </script> |
输出：
4
时间复杂性： 时间复杂度是（A）的总和 最大值 + 元素在arr中的最高出现率），因为如果频率大于1，则我们将多次处理该元素。
-哪里 最大值 是数组A[]中存在的最大元素。
空间复杂性： O（A） 最大值 )，A 最大值 是数组A[]中存在的最大元素。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
