Dada una array arr[] de n enteros, encuentre el máximo que maximiza la suma del valor de i*arr[i] donde i varía de 0 a n-1.
Ejemplos:
Input: arr[] = {8, 3, 1, 2}
Output: 29
Explanation: Lets look at all the rotations,
{8, 3, 1, 2} = 8*0 + 3*1 + 1*2 + 2*3 = 11
{3, 1, 2, 8} = 3*0 + 1*1 + 2*2 + 8*3 = 29
{1, 2, 8, 3} = 1*0 + 2*1 + 8*2 + 3*3 = 27
{2, 8, 3, 1} = 2*0 + 8*1 + 3*2 + 1*3 = 17
Input: arr[] = {3, 2, 1}
Output: 7
Explanation: Lets look at all the rotations,
{3, 2, 1} = 3*0 + 2*1 + 1*2 = 4
{2, 1, 3} = 2*0 + 1*1 + 3*2 = 7
{1, 3, 2} = 1*0 + 3*1 + 2*2 = 7
Método 1 : este método analiza la solución ingenua que requiere una cantidad de tiempo O (n 2 ).
La solución implica encontrar la suma de todos los elementos de la array en cada rotación y luego decidir el valor de suma máxima.
- Enfoque: una solución simple es probar todas las rotaciones posibles. Calcule la suma de i*arr[i] para cada rotación y devuelva la suma máxima.
- Algoritmo:
- Gire la array para todos los valores de 0 a n.
- Calcular la suma de cada rotación.
- Compruebe si la suma máxima es mayor que la suma actual y luego actualice la suma máxima.
Implementación:
C++
// A Naive C++ program to find maximum sum rotation
#include<bits/stdc++.h>
using namespace std;
// Returns maximum value of i*arr[i]
int maxSum(int arr[], int n)
{
// Initialize result
int res = INT_MIN;
// Consider rotation beginning with i
// for all possible values of i.
for (int i=0; i<n; i++)
{
// Initialize sum of current rotation
int curr_sum = 0;
// Compute sum of all values. We don't
// actually rotate the array, instead of that we compute the
// sum by finding indexes when arr[i] is
// first element
for (int j=0; j<n; j++)
{
int index = (i+j)%n;
curr_sum += j*arr[index];
}
// Update result if required
res = max(res, curr_sum);
}
return res;
}
// Driver code
int main()
{
int arr[] = {8, 3, 1, 2};
int n = sizeof(arr)/sizeof(arr[0]);
cout << maxSum(arr, n) << endl;
return 0;
}
Java
// A Naive Java program to find
// maximum sum rotation
import java.util.*;
import java.io.*;
class GFG {
// Returns maximum value of i*arr[i]
static int maxSum(int arr[], int n)
{
// Initialize result
int res = Integer.MIN_VALUE;
// Consider rotation beginning with i
// for all possible values of i.
for (int i = 0; i < n; i++)
{
// Initialize sum of current rotation
int curr_sum = 0;
// Compute sum of all values. We don't
// actually rotation the array, but compute
// sum by finding indexes when arr[i] is
// first element
for (int j = 0; j < n; j++)
{
int index = (i + j) % n;
curr_sum += j * arr[index];
}
// Update result if required
res = Math.max(res, curr_sum);
}
return res;
}
// Driver code
public static void main(String args[])
{
int arr[] = {8, 3, 1, 2};
int n = arr.length;
System.out.println(maxSum(arr, n));
}
}
// This code is contributed by Sahil_Bansall
Python3
# A Naive Python3 program to find # maximum sum rotation import sys # Returns maximum value of i * arr[i] def maxSum(arr, n): # Initialize result res = -sys.maxsize # Consider rotation beginning with i # for all possible values of i. for i in range(0, n): # Initialize sum of current rotation curr_sum = 0 # Compute sum of all values. We don't # actually rotation the array, but # compute sum by finding indexes when # arr[i] is first element for j in range(0, n): index = int((i + j)% n) curr_sum += j * arr[index] # Update result if required res = max(res, curr_sum) return res # Driver code arr = [8, 3, 1, 2] n = len(arr) print(maxSum(arr, n)) # This code is contributed by # Smitha Dinesh Semwal
C#
// A Naive C# program to find
// maximum sum rotation
using System;
class GFG {
// Returns maximum value of i*arr[i]
static int maxSum(int[] arr, int n)
{
// Initialize result
int res = int.MinValue;
// Consider rotation beginning with i
// for all possible values of i.
for (int i = 0; i < n; i++) {
// Initialize sum of current rotation
int curr_sum = 0;
// Compute sum of all values. We don't
// actually rotate the array, instead we compute
// sum by finding indexes when arr[i] is the
// first element
for (int j = 0; j < n; j++)
{
int index = (i + j) % n;
curr_sum += j * arr[index];
}
// Update result if required
res = Math.Max(res, curr_sum);
}
return res;
}
// Driver code
public static void Main()
{
int[] arr = { 8, 3, 1, 2 };
int n = arr.Length;
Console.WriteLine(maxSum(arr, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// A Naive PHP program to
// find maximum sum rotation
// Returns maximum value
// of i*arr[i]
function maxSum($arr, $n)
{
// Initialize result
$res = PHP_INT_MIN;
// Consider rotation beginning
// with i for all possible
// values of i.
for ($i = 0; $i < $n; $i++)
{
// Initialize sum of
// current rotation
$curr_sum = 0;
// Compute sum of all values.
// We don't actually rotate
// the array, but compute sum
// by finding indexes when
// arr[i] is first element
for ($j = 0; $j < $n; $j++)
{
$index = ($i + $j) % $n;
$curr_sum += $j * $arr[$index];
}
// Update result if required
$res = max($res, $curr_sum);
}
return $res;
}
// Driver code
$arr = array(8, 3, 1, 2);
$n = sizeof($arr);
echo maxSum($arr, $n), "\n";
// This code is contributed by ajit
?>
Javascript
<script>
// A Naive javascript program to find
// maximum sum rotation // Returns maximum value of i*arr[i]
function maxSum(arr , n) {
// Initialize result
var res = Number.MIN_VALUE;
// Consider rotation beginning with i
// for all possible values of i.
for (i = 0; i < n; i++) {
// Initialize sum of current rotation
var curr_sum = 0;
// Compute sum of all values. We don't
// actually rotation the array, but compute
// sum by finding indexes when arr[i] is
// first element
for (j = 0; j < n; j++) {
var index = (i + j) % n;
curr_sum += j * arr[index];
}
// Update result if required
res = Math.max(res, curr_sum);
}
return res;
}
// Driver code
var arr = [ 8, 3, 1, 2 ];
var n = arr.length;
document.write(maxSum(arr, n));
// This code contributed by umadevi9616
</script>
Producción
29
- Análisis de Complejidad:
- Complejidad del tiempo : O(n 2 )
- Espacio Auxiliar : O(1)
Método 2 : Este método analiza la solución eficiente que resuelve el problema en tiempo O(n). En la solución ingenua, los valores se calcularon para cada rotación. Entonces, si eso se puede hacer en tiempo constante, la complejidad disminuirá.
- Enfoque: El enfoque básico es calcular la suma de la nueva rotación a partir de las rotaciones anteriores. Esto trae a colación una similitud en la que solo los multiplicadores del primer y último elemento cambian drásticamente y el multiplicador de todos los demás elementos aumenta o disminuye en 1. Entonces, de esta manera, la suma de la próxima rotación se puede calcular a partir de la suma de la rotación actual.
- Algoritmo:
La idea es calcular el valor de una rotación usando valores de la rotación anterior. Cuando una array se rota en uno, los siguientes cambios ocurren en la suma de i*arr[i].- El multiplicador de arr[i-1] cambia de 0 a n-1, es decir, arr[i-1] * (n-1) se suma al valor actual.
- Los multiplicadores de otros términos se reducen en 1. Es decir, (cum_sum – arr[i-1]) se resta del valor actual donde cum_sum es la suma de todos los números.
next_val = curr_val - (cum_sum - arr[i-1]) + arr[i-1] * (n-1);
next_val = Value of ∑i*arr[i] after one rotation.
curr_val = Current value of ∑i*arr[i]
cum_sum = Sum of all array elements, i.e., ∑arr[i].
Lets take example {1, 2, 3}. Current value is 1*0+2*1+3*2
= 8. Shifting it by one will make it {2, 3, 1} and next value
will be 8 - (6 - 1) + 1*2 = 5 which is same as 2*0 + 3*1 + 1*2
Implementación:
C++
// An efficient C++ program to compute
// maximum sum of i*arr[i]
#include<bits/stdc++.h>
using namespace std;
int maxSum(int arr[], int n)
{
// Compute sum of all array elements
int cum_sum = 0;
for (int i=0; i<n; i++)
cum_sum += arr[i];
// Compute sum of i*arr[i] for initial
// configuration.
int curr_val = 0;
for (int i=0; i<n; i++)
curr_val += i*arr[i];
// Initialize result
int res = curr_val;
// Compute values for other iterations
for (int i=1; i<n; i++)
{
// Compute next value using previous
// value in O(1) time
int next_val = curr_val - (cum_sum - arr[i-1])
+ arr[i-1] * (n-1);
// Update current value
curr_val = next_val;
// Update result if required
res = max(res, next_val);
}
return res;
}
// Driver code
int main()
{
int arr[] = {8, 3, 1, 2};
int n = sizeof(arr)/sizeof(arr[0]);
cout << maxSum(arr, n) << endl;
return 0;
}
Java
// An efficient Java program to compute
// maximum sum of i*arr[i]
import java.io.*;
class GFG {
static int maxSum(int arr[], int n)
{
// Compute sum of all array elements
int cum_sum = 0;
for (int i = 0; i < n; i++)
cum_sum += arr[i];
// Compute sum of i*arr[i] for
// initial configuration.
int curr_val = 0;
for (int i = 0; i < n; i++)
curr_val += i * arr[i];
// Initialize result
int res = curr_val;
// Compute values for other iterations
for (int i = 1; i < n; i++)
{
// Compute next value using previous
// value in O(1) time
int next_val = curr_val - (cum_sum -
arr[i-1]) + arr[i-1] *
(n-1);
// Update current value
curr_val = next_val;
// Update result if required
res = Math.max(res, next_val);
}
return res;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {8, 3, 1, 2};
int n = arr.length;
System.out.println(maxSum(arr, n));
}
}
// This code is contributed by Prerna Saini
Python3
# An efficient Python3 program to # compute maximum sum of i * arr[i] def maxSum(arr, n): # Compute sum of all array elements cum_sum = 0 for i in range(0, n): cum_sum += arr[i] # Compute sum of i * arr[i] for # initial configuration. curr_val = 0 for i in range(0, n): curr_val += i * arr[i] # Initialize result res = curr_val # Compute values for other iterations for i in range(1, n): # Compute next value using previous # value in O(1) time next_val = (curr_val - (cum_sum - arr[i-1]) + arr[i-1] * (n-1)) # Update current value curr_val = next_val # Update result if required res = max(res, next_val) return res # Driver code arr = [8, 3, 1, 2] n = len(arr) print(maxSum(arr, n)) # This code is contributed by # Smitha Dinesh Semwal
C#
// An efficient C# program to compute
// maximum sum of i*arr[i]
using System;
class GFG {
static int maxSum(int []arr, int n)
{
// Compute sum of all array elements
int cum_sum = 0;
for (int i = 0; i < n; i++)
cum_sum += arr[i];
// Compute sum of i*arr[i] for
// initial configuration.
int curr_val = 0;
for (int i = 0; i < n; i++)
curr_val += i * arr[i];
// Initialize result
int res = curr_val;
// Compute values for other iterations
for (int i = 1; i < n; i++)
{
// Compute next value using previous
// value in O(1) time
int next_val = curr_val - (cum_sum -
arr[i - 1]) + arr[i - 1] *
(n - 1);
// Update current value
curr_val = next_val;
// Update result if required
res = Math.Max(res, next_val);
}
return res;
}
// Driver code
public static void Main()
{
int []arr = {8, 3, 1, 2};
int n = arr.Length;
Console.Write(maxSum(arr, n));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// An efficient PHP program to
// compute maximum sum of i*arr[i]
function maxSum($arr, $n)
{
// Compute sum of all
// array elements
$cum_sum = 0;
for ($i = 0; $i < $n; $i++)
$cum_sum += $arr[$i];
// Compute sum of i*arr[i]
// for initial configuration.
$curr_val = 0;
for ($i = 0; $i < $n; $i++)
$curr_val += $i * $arr[$i];
// Initialize result
$res = $curr_val;
// Compute values for
// other iterations
for ($i = 1; $i < $n; $i++)
{
// Compute next value using
// previous value in O(1) time
$next_val = $curr_val -
($cum_sum - $arr[$i - 1]) +
$arr[$i - 1] * ($n - 1);
// Update current value
$curr_val = $next_val;
// Update result if required
$res = max($res, $next_val);
}
return $res;
}
// Driver code
$arr = array(8, 3, 1, 2);
$n = sizeof($arr);
echo maxSum($arr, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// An efficient JavaScript program to compute
// maximum sum of i*arr[i]
function maxSum(arr, n)
{
// Compute sum of all array elements
let cum_sum = 0;
for (let i=0; i<n; i++)
cum_sum += arr[i];
// Compute sum of i*arr[i] for initial
// configuration.
let curr_val = 0;
for (let i=0; i<n; i++)
curr_val += i*arr[i];
// Initialize result
let res = curr_val;
// Compute values for other iterations
for (let i=1; i<n; i++)
{
// Compute next value using previous
// value in O(1) time
let next_val = curr_val - (cum_sum - arr[i-1])
+ arr[i-1] * (n-1);
// Update current value
curr_val = next_val;
// Update result if required
res = Math.max(res, next_val);
}
return res;
}
// Driver code
let arr = [8, 3, 1, 2];
let n = arr.length;
document.write(maxSum(arr, n) + "<br>");
// This code is contributed by Surbhi Tyagi.
</script>
Producción
29
- Análisis de complejidad:
- Complejidad temporal: O(n).
Dado que se necesita un ciclo de 0 an para comprobar todas las rotaciones y la suma de la rotación actual se calcula a partir de las rotaciones anteriores en tiempo O(1) . - Espacio Auxiliar: O(1).
Como no se requiere espacio adicional, la complejidad del espacio será O (1)
- Complejidad temporal: O(n).
Método 3 : El método discute la solución usando pivote en tiempo O(n). El método de pivote solo se puede usar en el caso de una array ordenada o rotada. Por ejemplo: {1, 2, 3, 4} o {2, 3, 4, 1}, {3, 4, 1, 2}, etc.
- Enfoque: supongamos el caso de una array ordenada. Como sabemos, para una array, la suma máxima será cuando la array se ordene en orden ascendente. En el caso de una array rotada ordenada, podemos rotar la array para hacerla en orden ascendente. Entonces, en este caso, se necesita encontrar el elemento pivote después del cual se puede calcular la suma máxima.
- Algoritmo:
- Encuentre el pivote de la array : si arr[i] > arr[(i+1)%n] entonces es el elemento pivote. (i+1)%n se utiliza para comprobar el último y el primer elemento.
- Después de obtener el pivote, la suma se puede calcular encontrando la diferencia con el pivote que será el multiplicador y multiplicándolo con el elemento actual mientras se calcula la suma.
Implementaciones:
C++
// C++ program to find maximum sum of all
// rotation of i*arr[i] using pivot.
#include <iostream>
using namespace std;
// fun declaration
int maxSum(int arr[], int n);
int findPivot(int arr[], int n);
// function definition
int maxSum(int arr[], int n)
{
int sum = 0;
int i;
int pivot = findPivot(arr, n);
// difference in pivot and index of
// last element of array
int diff = n - 1 - pivot;
for(i = 0; i < n; i++)
{
sum = sum + ((i + diff) % n) * arr[i];
}
return sum;
}
// function to find pivot
int findPivot(int arr[], int n)
{
int i;
for(i = 0; i < n; i++)
{
if(arr[i] > arr[(i + 1) % n])
return i;
}
}
// Driver code
int main(void)
{
// rotated input array
int arr[] = {8, 3, 1, 2};
int n = sizeof(arr) / sizeof(int);
int max = maxSum(arr, n);
cout << max;
return 0;
}
// This code is contributed by Shubhamsingh10
C
// C program to find maximum sum of all
// rotation of i*arr[i] using pivot.
#include<stdio.h>
// fun declaration
int maxSum(int arr[], int n);
int findPivot(int arr[], int n);
// function definition
int maxSum(int arr[], int n)
{
int sum = 0;
int i;
int pivot = findPivot(arr, n);
// difference in pivot and index of
// last element of array
int diff = n - 1 - pivot;
for(i = 0; i < n; i++)
{
sum= sum + ((i + diff) % n) * arr[i];
}
return sum;
}
// function to find pivot
int findPivot(int arr[], int n)
{
int i;
for(i = 0; i < n; i++)
{
if(arr[i] > arr[(i + 1) % n])
return i;
}
}
// Driver code
int main(void)
{
// rotated input array
int arr[] = {8, 3, 1, 2};
int n = sizeof(arr) / sizeof(int);
int max = maxSum(arr, n);
printf("%d", max);
return 0;
}
Java
// Java program to find maximum sum
// of all rotation of i*arr[i] using pivot.
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
// function definition
static int maxSum(int arr[], int n)
{
int sum = 0;
int i;
int pivot = findPivot(arr, n);
// difference in pivot and index of
// last element of array
int diff = n - 1 - pivot;
for(i = 0; i < n; i++)
{
sum= sum + ((i + diff) % n) * arr[i];
}
return sum;
}
// function to find pivot
static int findPivot(int arr[], int n)
{
int i;
for(i = 0; i < n; i++)
{
if(arr[i] > arr[(i + 1) % n])
return i;
}
return 0;
}
// Driver code
public static void main(String args[])
{
// rotated input array
int arr[] = {8, 3, 1, 2};
int n = arr.length;
int max = maxSum(arr,n);
System.out.println(max);
}
}
Python3
# Python3 program to find maximum sum of # all rotation of i*arr[i] using pivot. # function definition def maxSum(arr, n) : sum = 0 pivot = findPivot(arr, n) # difference in pivot and index # of last element of array diff = n - 1 - pivot for i in range(n) : sum = sum + ((i + diff) % n) * arr[i]; return sum # function to find pivot def findPivot(arr, n) : for i in range(n) : if(arr[i] > arr[(i + 1) % n]) : return i; # Driver code if __name__ == "__main__" : # rotated input array arr = [8, 3, 1, 2] n= len(arr) max= maxSum(arr, n) print(max) # This code is contributed by Ryuga
C#
// C# program to find maximum sum
// of all rotation of i*arr[i] using pivot.
using System;
class GFG
{
// function definition
public static int maxSum(int[] arr, int n)
{
int sum = 0;
int i;
int pivot = findPivot(arr,n);
// difference in pivot and index of
// last element of array
int diff = n - 1 - pivot;
for (i = 0;i < n;i++)
{
sum = sum + ((i + diff) % n) * arr[i];
}
return sum;
}
// function to find pivot
public static int findPivot(int[] arr, int n)
{
int i;
for (i = 0; i < n; i++)
{
if (arr[i] > arr[(i + 1) % n])
{
return i;
}
}
return 0;
}
// Driver code
public static void Main(string[] args)
{
// rotated input array
int[] arr = new int[] {8, 3, 1, 2};
int n = arr.Length;
int max = maxSum(arr,n);
Console.WriteLine(max);
}
}
// This code is contributed by Shrikant13
PHP
<?php
// PHP program to find maximum sum
// of all rotation of i*arr[i] using pivot.
// function definition
function maxSum($arr, $n)
{
$sum = 0;
$pivot = findPivot($arr, $n);
// difference in pivot and index of
// last element of array
$diff = $n - 1 - $pivot;
for($i = 0; $i < $n; $i++)
{
$sum = $sum + (($i + $diff) %
$n) * $arr[$i];
}
return $sum;
}
// function to find pivot
function findPivot($arr, $n)
{
for($i = 0; $i < $n; $i++)
{
if($arr[$i] > $arr[($i + 1) % $n])
return $i;
}
return 0;
}
// Driver code
// rotated input array
$arr = array(8, 3, 1, 2);
$n = sizeof($arr);
$max = maxSum($arr, $n);
echo $max;
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>
Javascript
<script>
// js program to find maximum sum
// of all rotation of i*arr[i] using pivot.
// function definition
function maxSum(arr, n)
{
let sum = 0;
let i;
let pivot = findPivot(arr,n);
// difference in pivot and index of
// last element of array
let diff = n - 1 - pivot;
for (i = 0;i < n;i++)
{
sum = sum + ((i + diff) % n) * arr[i];
}
return sum;
}
// function to find pivot
function findPivot(arr, n)
{
let i;
for (i = 0; i < n; i++)
{
if (arr[i] > arr[(i + 1) % n])
{
return i;
}
}
return 0;
}
// Driver code
// rotated input array
let arr = [8, 3, 1, 2];
let n = arr.length;
let ma = maxSum(arr,n);
document.write(ma);
// This code is contributed by mohit kumar 29.
</script>
Producción
29
- Análisis de complejidad:
- Complejidad de tiempo: O (n)
Ya que solo se necesitaba un ciclo para atravesar de 0 an para encontrar el pivote. Para encontrar la suma se necesitaba otro bucle, por lo que la complejidad sigue siendo O(n) . - Espacio Auxiliar : O(1).
No requerimos espacio adicional para que el espacio auxiliar sea O (1)
- Complejidad de tiempo: O (n)
Este artículo es una contribución de Shubham Joshi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA