Dado un arreglo A[] que consta de N enteros positivos, la tarea es construir un arreglo B[] de tamaño N que tenga la máxima suma posible de elementos del arreglo que satisfagan los siguientes criterios para cada índice i :
- El elemento de array B[i] debe ser menor o igual que A[i] .
- Para todo índice i , B[i] debe ser mayor que todos los elementos presentes tanto a su izquierda como a su derecha.
Ejemplos:
Entrada: A[] = {10, 6, 8}
Salida: 10 6 6
Explicación:
Considere la array B[] como {10, 6, 6} que satisface los criterios dados, como se muestra a continuación, con la suma máxima de elementos:
- Para el elemento de array B[0](= 10): el elemento máximo a la izquierda y a la derecha del índice 0 en la array B[] es -1 y 6 respectivamente y B[0](= 10) es menor que o igual a -1.
- Para el elemento de array B[1](= 6): el elemento máximo a la izquierda y a la derecha del índice 1 en la array B[] es 10 y 6 respectivamente y B[1](= 6) es menor o igual a 6
- Para el elemento de array B[2](= 6): el elemento máximo a la izquierda y a la derecha del índice 2 en la array B[] es 10 y -1 respectivamente y B[2](= 6) es menor que o igual a -1.
Entrada: A[ ] = {1, 2, 3, 1}
Salida: 1 2 3 1
Enfoque: El problema dado se puede resolver observando el hecho de que siempre hay un elemento máximo en la array que primero crece y luego decrece monótonamente . Por lo tanto, la idea es hacer que cada elemento de la array de la nueva array B[] sea máximo uno por uno y luego verificar la suma máxima. Siga los pasos a continuación para resolver el problema dado:
- Inicialice los arreglos, digamos arrA[] y ans[] que almacenan los elementos del arreglo A[] y el arreglo resultante respectivamente.
- Inicialice una variable, digamos maxSum como 0 que almacena la suma máxima de elementos de array.
- Iterar sobre el rango [0, N] y realizar los siguientes pasos:
- Inicialice una array, digamos arrB[] que puede almacenar la array resultante.
- Asigne todos los elementos de la array arrB[i] en orden monótonamente creciente hasta cada índice i .
- Asigne todos los elementos de la array arrB[i] en orden monótonamente decreciente sobre el rango [i, N] .
- Ahora, busque la suma de la array arrB[] y, si la suma es mayor que maxSum , actualice maxSum y la array ans[] a la suma actual y la array actual arrB[] construida.
- Después de completar los pasos anteriores, imprima la array arrB[] como la array resultante.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
10 6 6
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA