Generate an array of maximum sum such that each element exceeds all elements present either on its left or right
Given an array A[] consisting of N positive integers, the task is to construct an array B[] of size N having maximum possible sum of array elements satisfying the following criteria for every index i:
- The array element B[i] must be less than or equal to A[i].
- For every index i, B[i] must be greater than all elements present either on its left or its right.
Examples:
Input: A[] = {10, 6, 8}
Output: 10 6 6
Explanation:
Consider the array B[] as {10, 6, 6} that satisfy the given criteria as shown below having the maximum sum of elements:
- For array element B[0](= 10): The maximum element to the left and the right of the index 0 in the array B[] is -1 and 6 respectively and B[0](= 10) is less than or equal to -1.
- For array element B[1](= 6): The maximum element to the left and the right of the index 1 in the array B[] is 10 and 6 respectively and B[1](= 6) is less than or equal to 6.
- For array element B[2](= 6): The maximum element to the left and the right of the index 2 in the array B[] is 10 and -1 respectively and B[2](= 6) is less than or equal to -1.
Input: A[ ] = {1, 2, 3, 1}
Output: 1 2 3 1
Approach: The given problem can be solved by observing the fact that there is always a maximum element in the array which is first increasing and then monotonically decreasing. Therefore, the idea is to make every array element of the new array B[] maximum one by one and then check for the maximum sum. Follow the steps below to solve the given problem:
- Initialize the arrays, say arrA[] and ans[] that stores the array elements A[] and the resultant array respectively.
- Initialize a variable, say maxSum as 0 that stores the maximum sum of array elements.
- Iterate over the range [0, N] and perform the following steps:
- Initialize an array, say arrB[] that can stores the resultant array.
- Assign all the array element arrB[i] in the monotonically increasing order till every index i.
- Assign all the array element arrB[i] in the monotonically decreasing order over then range [i, N].
- Now, find the sum of array arrB[] and if the sum is greater than maxSum then update the maxSum and the array ans[] to the current sum and current array arrB[] constructed.
- After completing the above steps, print the array arrB[] as the resultant array.
Below is the implementation of the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to construct the array // having maximum sum satisfying the // given criteria void maximumSumArray( int arr[], int N) { // Declaration of the array arrA[] // and ans[] vector< int > arrA(N), ans(N); // Stores the maximum sum of the // resultant array int maxSum = 0; // Initialize the array arrA[] for ( int i = 0; i < N; i++) arrA[i] = arr[i]; // Traversing the array arrA[] for ( int i = 0; i < N; i++) { // Initialize the array arrB[] vector< int > arrB(N); int maximum = arrA[i]; // Assign the maximum element // to the current element arrB[i] = maximum; // Form the first increasing // till every index i for ( int j = i - 1; j >= 0; j--) { arrB[j] = min(maximum, arrA[j]); maximum = arrB[j]; } // Make the current element // as the maximum element maximum = arrA[i]; // Forming decreasing from the // index i + 1 to the index N for ( int j = i + 1; j < N; j++) { arrB[j] = min(maximum, arrA[j]); maximum = arrB[j]; } // Initialize the sum int sum = 0; // Find the total sum for ( int j = 0; j < N; j++) sum += arrB[j]; // Check if the total sum is // at least the sum found // then make ans as ansB if (sum > maxSum) { maxSum = sum; ans = arrB; } } // Print the final array formed for ( int val : ans) { cout << val << " " ; } } // Driver Code int main() { int A[] = { 10, 6, 8 }; int N = sizeof (A) / sizeof (A[0]); maximumSumArray(A, N); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to construct the array // having maximum sum satisfying the // given criteria static void maximumSumArray( int arr[], int N) { // Declaration of the array arrA[] // and ans[] int [] arrA = new int [(N)]; int [] ans = new int [(N)]; // Stores the maximum sum of the // resultant array int maxSum = 0 ; // Initialize the array arrA[] for ( int i = 0 ; i < N; i++) arrA[i] = arr[i]; // Traversing the array arrA[] for ( int i = 0 ; i < N; i++) { // Initialize the array arrB[] int [] arrB = new int [(N)]; int maximum = arrA[i]; // Assign the maximum element // to the current element arrB[i] = maximum; // Form the first increasing // till every index i for ( int j = i - 1 ; j >= 0 ; j--) { arrB[j] = Math.min(maximum, arrA[j]); maximum = arrB[j]; } // Make the current element // as the maximum element maximum = arrA[i]; // Forming decreasing from the // index i + 1 to the index N for ( int j = i + 1 ; j < N; j++) { arrB[j] = Math.min(maximum, arrA[j]); maximum = arrB[j]; } // Initialize the sum int sum = 0 ; // Find the total sum for ( int j = 0 ; j < N; j++) sum += arrB[j]; // Check if the total sum is // at least the sum found // then make ans as ansB if (sum > maxSum) { maxSum = sum; ans = arrB; } } // Print the final array formed for ( int val : ans) { System.out.print(val + " " ); } } // Driver Code public static void main(String[] args) { int A[] = { 10 , 6 , 8 }; int N = A.length; maximumSumArray(A, N); } } // This code is contributed by splevel62. |
Python3
# Python program for the above approach; # Function to construct the array # having maximum sum satisfying the # given criteria def maximumSumArray(arr, N): # Declaration of the array arrA[] # and ans[] arrA = [ 0 ] * N ans = [ 0 ] * N # Stores the maximum sum of the # resultant array maxSum = 0 ; # Initialize the array arrA[] for i in range (N): arrA[i] = arr[i]; # Traversing the array arrA[] for i in range (N): # Initialize the array arrB[] arrB = [ 0 ] * N maximum = arrA[i]; # Assign the maximum element # to the current element arrB[i] = maximum; temp = 0 # Form the first increasing # till every index i for j in range (i - 1 , - 1 , - 1 ): arrB[j] = min (maximum, arrA[j]); maximum = arrB[j]; temp = j # Make the current element # as the maximum element maximum = arrA[i]; # Forming decreasing from the # index i + 1 to the index N for j in range (i + 1 , N): arrB[j] = min (maximum, arrA[j]); maximum = arrB[j]; # Initialize the sum sum = 0 ; # Find the total sum for j in range (N): sum + = arrB[j]; # Check if the total sum is # at least the sum found # then make ans as ansB if ( sum > maxSum): maxSum = sum ; ans = arrB; # Print the final array formed for val in ans: print (val); # Driver Code A = [ 10 , 6 , 8 ]; N = len (A) maximumSumArray(A, N); # This code is contributed by _Saurabh_Jaiswal |
C#
// C# code for the above approach using System; using System.Collections.Generic; class GFG{ // Function to construct the array // having maximum sum satisfying the // given criteria static void maximumSumArray( int []arr, int N) { // Declaration of the array arrA[] // and ans[] int []arrA = new int [N]; int []ans = new int [N]; // Stores the maximum sum of the // resultant array int maxSum = 0; // Initialize the array arrA[] for ( int i = 0; i < N; i++) arrA[i] = arr[i]; // Traversing the array arrA[] for ( int i = 0; i < N; i++) { // Initialize the array arrB[] int []arrB = new int [N]; int maximum = arrA[i]; // Assign the maximum element // to the current element arrB[i] = maximum; // Form the first increasing // till every index i for ( int j = i - 1; j >= 0; j--) { arrB[j] = Math.Min(maximum, arrA[j]); maximum = arrB[j]; } // Make the current element // as the maximum element maximum = arrA[i]; // Forming decreasing from the // index i + 1 to the index N for ( int j = i + 1; j < N; j++) { arrB[j] = Math.Min(maximum, arrA[j]); maximum = arrB[j]; } // Initialize the sum int sum = 0; // Find the total sum for ( int j = 0; j < N; j++) sum += arrB[j]; // Check if the total sum is // at least the sum found // then make ans as ansB if (sum > maxSum) { maxSum = sum; ans = arrB; } } // Print the final array formed foreach ( int val in ans) { Console.Write(val + " " ); } } // Driver Code public static void Main() { int []A = { 10, 6, 8 }; int N = A.Length; maximumSumArray(A, N); } } // This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript program for the above approach; // Function to construct the array // having maximum sum satisfying the // given criteria function maximumSumArray(arr, N) { // Declaration of the array arrA[] // and ans[] let arrA = new Array(N); let ans = new Array(N); // Stores the maximum sum of the // resultant array let maxSum = 0; // Initialize the array arrA[] for (let i = 0; i < N; i++) arrA[i] = arr[i]; // Traversing the array arrA[] for (let i = 0; i < N; i++) { // Initialize the array arrB[] let arrB = new Array(N); let maximum = arrA[i]; // Assign the maximum element // to the current element arrB[i] = maximum; // Form the first increasing // till every index i for (let j = i - 1; j >= 0; j--) { arrB[j] = Math.min(maximum, arrA[j]); maximum = arrB[j]; } // Make the current element // as the maximum element maximum = arrA[i]; // Forming decreasing from the // index i + 1 to the index N for (let j = i + 1; j < N; j++) { arrB[j] = Math.min(maximum, arrA[j]); maximum = arrB[j]; } // Initialize the sum let sum = 0; // Find the total sum for (let j = 0; j < N; j++) sum += arrB[j]; // Check if the total sum is // at least the sum found // then make ans as ansB if (sum > maxSum) { maxSum = sum; ans = arrB; } } // Print the final array formed for (let val of ans) { document.write(val + " " ); } } // Driver Code let A = [ 10, 6, 8 ]; let N = A.length; maximumSumArray(A, N); // This code is contributed by Potta Lokesh </script> |
10 6 6
Time Complexity: O(N2)
Auxiliary Space: O(N)
Contact Us