Suma máxima de subarreglo en un arreglo creado después de una concatenación repetida | Conjunto-2

Dado un arreglo arr[] que consta de N enteros y un entero positivo K , la tarea es encontrar la suma más grande de cualquier subarreglo contiguo en el arreglo modificado formado al repetir el arreglo dado K veces.

Ejemplos: 

Entrada: arr[] = {-1, 10, 20}, K = 2
Salida: 59
Explicación:
Después de concatenar la array dos veces, la array se modifica a {-1, 10, 20, -1, 10, 20}. 
El subarreglo con la suma máxima está sobre el rango [1, 5], es decir, {10, 20, -1, 10, 20}.

Entrada: arr[] = {10, 20, -30, -1, 40}, K =10
Salida: 391

Enfoque ingenuo: el enfoque más simple para resolver el problema se analiza en el Conjunto-1 .

Enfoque eficiente: el enfoque anterior se puede optimizar aún más en función de las siguientes observaciones:

1. Si la suma de la array es mayor que 0 , contribuirá a la respuesta. De lo contrario, no es bueno incluir todos los elementos del arreglo en el subarreglo máximo.
2. Supongamos que las variables maxPrefix y maxSufix almacenan la suma máxima de prefijos y la suma máxima de sufijos de una array repetida dos veces.
3. Por lo tanto, el subarreglo de suma máxima se puede formar de cualquiera de las siguientes maneras:
   1. Agregar los elementos del maxSufix de la array formada al combinar las dos primeras arrays y luego agregar las N-2 arrays restantes.
   2. Primero, agregando las arrays N-2 y luego agregando los elementos del maxPrefix de la array formada al combinar las dos últimas arrays.
   3. Tomando todos los elementos del subarreglo de suma máxima de un arreglo repetido dos veces.

Siga los pasos a continuación para resolver el problema:

• Encuentre la suma de la array arr[] y guárdela en una variable, digamos sum1 .
• Inicialice una variable, diga sum y ans como 0 para almacenar la suma máxima actual y la respuesta.
• Si K = 1 , imprima la suma máxima de subarreglo del arreglo arr[].
• De lo contrario, inserte los elementos de la array arr[] desde [0, N-1] en la array, digamos V[] dos veces.
• Encuentre la suma máxima de prefijos de la array V[] y guárdela en una variable, digamos maxPrefix .
• Encuentre la suma máxima de sufijos de la array V[] y guárdela en una variable, digamos maxSufix .
• Iterar en el rango [0, 2*N-1] usando la variable i y realizar los siguientes pasos:
  • Modifique el valor de sum como max(sum + arr[i], arr[i]) y actualice el valor de ans como max(ans, sum).
• Si sum1 > 0, actualice ans al máximo de {ans, sum1*(K-2)+maxPrefix, sum1*(K-2)*maxSufix}.
• Finalmente, después de completar los pasos anteriores, imprima el valor de ans como respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find contiguous subarray with
// maximum sum if array is repeated K times
int maxSubArraySumRepeated(int arr[], int N, int K)
{
    // Store the sum of the array arr[]
    int sum = 0;
 
    // Traverse the array and find sum
    for (int i = 0; i < N; i++)
        sum += arr[i];
 
    int curr = arr[0];
 
    // Store the answer
    int ans = arr[0];
 
    // If K = 1
    if (K == 1) {
 
        // Apply Kadane algorithm to find sum
        for (int i = 1; i < N; i++) {
            curr = max(arr[i], curr + arr[i]);
            ans = max(ans, curr);
        }
        // Return the answer
        return ans;
    }
 
    // Stores the twice repeated array
    vector<int> V;
 
    // Traverse the range [0, 2*N]
    for (int i = 0; i < 2 * N; i++) {
        V.push_back(arr[i % N]);
    }
 
    // Stores the maximum suffix sum
    int maxSuf = V[0];
 
    // Stores the maximum prefix sum
    int maxPref = V[2 * N - 1];
 
    curr = V[0];
 
    for (int i = 1; i < 2 * N; i++) {
        curr += V[i];
        maxPref = max(maxPref, curr);
    }
 
    curr = V[2 * N - 1];
    for (int i = 2 * N - 2; i >= 0; i--) {
        curr += V[i];
        maxSuf = max(maxSuf, curr);
    }
 
    curr = V[0];
    // Apply Kadane algorithm for 2 repetition
    // of the array
    for (int i = 1; i < 2 * N; i++) {
        curr = max(V[i], curr + V[i]);
        ans = max(ans, curr);
    }
 
    // If the sum of the array is greater than 0
    if (sum > 0) {
        int temp = 1LL * sum * (K - 2);
        ans = max(ans, max(temp + maxPref, temp + maxSuf));
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
    // Given Input
    int arr[] = { 10, 20, -30, -1, 40 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 10;
 
    // Function Call
    cout << maxSubArraySumRepeated(arr, N, K);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to find contiguous subarray with
// maximum sum if array is repeated K times
static int maxSubArraySumRepeated(int[] arr, int N,
                                  int K)
{
     
    // Store the sum of the array arr[]
    int sum = 0;
 
    // Traverse the array and find sum
    for(int i = 0; i < N; i++)
        sum += arr[i];
 
    int curr = arr[0];
 
    // Store the answer
    int ans = arr[0];
 
    // If K = 1
    if (K == 1)
    {
         
        // Apply Kadane algorithm to find sum
        for(int i = 1; i < N; i++)
        {
            curr = Math.max(arr[i], curr + arr[i]);
            ans = Math.max(ans, curr);
        }
         
        // Return the answer
        return ans;
    }
 
    // Stores the twice repeated array
    ArrayList<Integer> V = new  ArrayList<Integer>();
 
    // Traverse the range [0, 2*N]
    for(int i = 0; i < 2 * N; i++)
    {
        V.add(arr[i % N]);
    }
 
    // Stores the maximum suffix sum
    int maxSuf = V.get(0);
 
    // Stores the maximum prefix sum
    int maxPref = V.get(2 * N - 1);
 
    curr = V.get(0);
 
    for(int i = 1; i < 2 * N; i++)
    {
        curr += V.get(i);
        maxPref = Math.max(maxPref, curr);
    }
 
    curr = V.get(2 * N - 1);
    for(int i = 2 * N - 2; i >= 0; i--)
    {
        curr += V.get(i);
        maxSuf = Math.max(maxSuf, curr);
    }
 
    curr = V.get(0);
     
    // Apply Kadane algorithm for 2 repetition
    // of the array
    for(int i = 1; i < 2 * N; i++)
    {
        curr = Math.max(V.get(i), curr + V.get(i));
        ans = Math.max(ans, curr);
    }
 
    // If the sum of the array is greater than 0
    if (sum > 0)
    {
        int temp = sum * (K - 2);
        ans = Math.max(ans, Math.max(temp + maxPref,
                                     temp + maxSuf));
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void main(String args[])
{
     
    // Given Input
    int []arr = { 10, 20, -30, -1, 40 };
    int N = arr.length;
    int K = 10;
 
    // Function Call
    System.out.print(maxSubArraySumRepeated(arr, N, K));
}
}
 
// This code is contributed by SURENDRA_GANGWAR

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
    // Function to find contiguous subarray with
    // maximum sum if array is repeated K times
    static int maxSubArraySumRepeated(int[] arr, int N,
                                      int K)
    {
        // Store the sum of the array arr[]
        int sum = 0;
 
        // Traverse the array and find sum
        for (int i = 0; i < N; i++)
            sum += arr[i];
 
        int curr = arr[0];
 
        // Store the answer
        int ans = arr[0];
 
        // If K = 1
        if (K == 1) {
 
            // Apply Kadane algorithm to find sum
            for (int i = 1; i < N; i++) {
                curr = Math.Max(arr[i], curr + arr[i]);
                ans = Math.Max(ans, curr);
            }
            // Return the answer
            return ans;
        }
 
        // Stores the twice repeated array
        List<int> V = new List<int>();
 
        // Traverse the range [0, 2*N]
        for (int i = 0; i < 2 * N; i++) {
            V.Add(arr[i % N]);
        }
 
        // Stores the maximum suffix sum
        int maxSuf = V[0];
 
        // Stores the maximum prefix sum
        int maxPref = V[2 * N - 1];
 
        curr = V[0];
 
        for (int i = 1; i < 2 * N; i++) {
            curr += V[i];
            maxPref = Math.Max(maxPref, curr);
        }
 
        curr = V[2 * N - 1];
        for (int i = 2 * N - 2; i >= 0; i--) {
            curr += V[i];
            maxSuf = Math.Max(maxSuf, curr);
        }
 
        curr = V[0];
        // Apply Kadane algorithm for 2 repetition
        // of the array
        for (int i = 1; i < 2 * N; i++) {
            curr = Math.Max(V[i], curr + V[i]);
            ans = Math.Max(ans, curr);
        }
 
        // If the sum of the array is greater than 0
        if (sum > 0) {
            int temp = sum * (K - 2);
            ans = Math.Max(ans, Math.Max(temp + maxPref,
                                         temp + maxSuf));
        }
 
        // Return the answer
        return ans;
    }
 
    // Driver Code
    public static void Main()
    {
        // Given Input
        int[] arr = { 10, 20, -30, -1, 40 };
        int N = arr.Length;
        int K = 10;
 
        // Function Call
        Console.WriteLine(
            maxSubArraySumRepeated(arr, N, K));
    }
}
 
// This code is contributed by ukasp.

# python 3 program for the above approach
 
# Function to find contiguous subarray with
# maximum sum if array is repeated K times
def maxSubArraySumRepeated(arr, N, K):
   
    # Store the sum of the array arr[]
    sum = 0
 
    # Traverse the array and find sum
    for i in range(N):
        sum += arr[i]
 
    curr = arr[0]
 
    # Store the answer
    ans = arr[0]
 
    # If K = 1
    if (K == 1):
       
        # Apply Kadane algorithm to find sum
        for i in range(1,N,1):
            curr = max(arr[i], curr + arr[i])
            ans = max(ans, curr)
 
        # Return the answer
        return ans
 
    # Stores the twice repeated array
    V = []
 
    # Traverse the range [0, 2*N]
    for i in range(2 * N):
        V.append(arr[i % N])
 
    # Stores the maximum suffix sum
    maxSuf = V[0]
 
    # Stores the maximum prefix sum
    maxPref = V[2 * N - 1]
 
    curr = V[0]
 
    for i in range(1,2 * N,1):
        curr += V[i]
        maxPref = max(maxPref, curr)
 
    curr = V[2 * N - 1]
    i = 2 * N - 2
    while(i >= 0):
        curr += V[i]
        maxSuf = max(maxSuf, curr)
        i -= 1
 
    curr = V[0]
     
    # Apply Kadane algorithm for 2 repetition
    # of the array
    for i in range(1, 2 * N, 1):
        curr = max(V[i], curr + V[i])
        ans = max(ans, curr)
 
    # If the sum of the array is greater than 0
    if (sum > 0):
        temp = sum * (K - 2)
        ans = max(ans, max(temp + maxPref, temp + maxSuf))
 
    # Return the answer
    return ans
 
# Driver Code
if __name__ == '__main__':
   
    # Given Input
    arr = [10, 20, -30, -1, 40]
    N = len(arr)
    K = 10
 
    # Function Call
    print(maxSubArraySumRepeated(arr, N, K))
     
    # This code is contributed by ipg2016107.

<script>
 
// JavaScript program for the above approach
 
 
// Function to find contiguous subarray with
// maximum sum if array is repeated K times
function maxSubArraySumRepeated(arr, N, K) {
    // Store the sum of the array arr[]
    let sum = 0;
 
    // Traverse the array and find sum
    for (let i = 0; i < N; i++)
        sum += arr[i];
 
    let curr = arr[0];
 
    // Store the answer
    let ans = arr[0];
 
    // If K = 1
    if (K == 1) {
 
        // Apply Kadane algorithm to find sum
        for (let i = 1; i < N; i++) {
            curr = Math.max(arr[i], curr + arr[i]);
            ans = Math.max(ans, curr);
        }
        // Return the answer
        return ans;
    }
 
    // Stores the twice repeated array
    let V = [];
 
    // Traverse the range [0, 2*N]
    for (let i = 0; i < 2 * N; i++) {
        V.push(arr[i % N]);
    }
 
    // Stores the maximum suffix sum
    let maxSuf = V[0];
 
    // Stores the maximum prefix sum
    let maxPref = V[2 * N - 1];
 
    curr = V[0];
 
    for (let i = 1; i < 2 * N; i++) {
        curr += V[i];
        maxPref = Math.max(maxPref, curr);
    }
 
    curr = V[2 * N - 1];
    for (let i = 2 * N - 2; i >= 0; i--) {
        curr += V[i];
        maxSuf = Math.max(maxSuf, curr);
    }
 
    curr = V[0];
    // Apply Kadane algorithm for 2 repetition
    // of the array
    for (let i = 1; i < 2 * N; i++) {
        curr = Math.max(V[i], curr + V[i]);
        ans = Math.max(ans, curr);
    }
 
    // If the sum of the array is greater than 0
    if (sum > 0) {
        let temp = sum * (K - 2);
        ans = Math.max(ans, Math.max(temp + maxPref, temp + maxSuf));
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
 
// Given Input
let arr = [10, 20, -30, -1, 40];
let N = arr.length;
let K = 10;
 
// Function Call
document.write(maxSubArraySumRepeated(arr, N, K));
 
</script>

391

Complejidad temporal: O(N)
Espacio auxiliar: O(N)