Encuentre el valor mínimo de K para maximizar la suma de elementos en índices que son múltiplos de K

Dada una array arr[] de N enteros, la tarea es encontrar el valor mínimo de K tal que la suma de los elementos de los índices que son múltiplos de K sea la máxima posible.

Ejemplo:

Entrada: arr[] = {-3, 4}
Salida: 2
Explicación: Para la array dada, si el valor de K = 1, entonces los múltiplos de K son {1, 2} que se suma a arr[1] + arr[2] = -3 + 4 = 1. Para K = 2, el múltiplo válido de K es 2 y por tanto la suma es arr[2] = 4, que es el máximo posible. Por lo tanto, K = 2 es una respuesta válida. 

Entrada: arr[] = {-1, -2, -3}
Salida: 2

Planteamiento: El problema planteado se puede resolver mediante una criba similar a la de Eratóstenes . La idea es calcular la suma de todos los valores posibles de K en el rango [1, N] iterando sobre cada múltiplo de K como se hizo al marcar los elementos no primos en el tamiz. El valor de K que da la suma máxima es la respuesta requerida.

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

// C++ Program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum K such that
// the sum of elements on indices that
// are multiples of K is maximum possible
int maxSum(int arr[], int N)
{
    // Stores the maximum sum and
    // respective K value
    int maxSum = INT_MIN, ans = -1;
 
    // Loop to iterate over all
    // value of K in range [1, N]
    for (int K = 1; K <= N; K++) {
        int sum = 0;
 
        // Iterating over all
        // multiples of K
        for (int i = K; i <= N; i += K) {
            sum += arr[i - 1];
        }
 
        // Update Maximum Sum
        if (sum > maxSum) {
            maxSum = sum;
            ans = K;
        }
    }
 
    // Return Answer
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { -1, -2, -3 };
    int N = sizeof(arr) / sizeof(int);
 
    cout << maxSum(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to find minimum K such that
// the sum of elements on indices that
// are multiples of K is maximum possible
static int maxSum(int arr[], int N)
{
     
    // Stores the maximum sum and
    // respective K value
    int maxSum = Integer.MIN_VALUE, ans = -1;
 
    // Loop to iterate over all
    // value of K in range [1, N]
    for(int K = 1; K <= N; K++)
    {
        int sum = 0;
 
        // Iterating over all
        // multiples of K
        for(int i = K; i <= N; i += K)
        {
            sum += arr[i - 1];
        }
 
        // Update Maximum Sum
        if (sum > maxSum)
        {
            maxSum = sum;
            ans = K;
        }
    }
 
    // Return Answer
    return ans;
}
 
// Driver Code
public static void main(String args[])
{
    int arr[] = { -1, -2, -3 };
    int N = arr.length;
 
    System.out.println(maxSum(arr, N));
}
}
 
// This code is contributed by Samim Hossain Mondal.

# Python program for the above approach
import sys
 
# Function to find minimum K such that
# the sum of elements on indices that
# are multiples of K is maximum possible
def maxSum(arr, N):
 
    # Stores the maximum sum and
    # respective K value
    maxSum = -sys.maxsize;
    ans = -1;
 
    # Loop to iterate over all
    # value of K in range [1, N]
    for K in range(1,N+1):
        sum = 0;
 
        # Iterating over all
        # multiples of K
        for i in range(K, N + 1,K):
            sum += arr[i - 1];
         
        # Update Maximum Sum
        if (sum > maxSum):
            maxSum = sum;
            ans = K;
         
    # Return Answer
    return ans;
 
# Driver Code
if __name__ == '__main__':
    arr = [ -1, -2, -3 ];
    N = len(arr);
 
    print(maxSum(arr, N));
 
# This code is contributed by gauravrajput1

// C# program for the above approach
using System;
 
public class GFG{
 
  // Function to find minimum K such that
  // the sum of elements on indices that
  // are multiples of K is maximum possible
  static int maxSum(int []arr, int N)
  {
 
    // Stores the maximum sum and
    // respective K value
    int maxSum = int.MinValue, ans = -1;
 
    // Loop to iterate over all
    // value of K in range [1, N]
    for(int K = 1; K <= N; K++)
    {
      int sum = 0;
 
      // Iterating over all
      // multiples of K
      for(int i = K; i <= N; i += K)
      {
        sum += arr[i - 1];
      }
 
      // Update Maximum Sum
      if (sum > maxSum)
      {
        maxSum = sum;
        ans = K;
      }
    }
 
    // Return Answer
    return ans;
  }
 
  // Driver Code
  public static void Main(String []args)
  {
    int []arr = { -1, -2, -3 };
    int N = arr.Length;
 
    Console.WriteLine(maxSum(arr, N));
  }
}
 
// This code is contributed by 29AjayKumar

<script>
      // JavaScript code for the above approach
 
 
      // Function to find minimum K such that
      // the sum of elements on indices that
      // are multiples of K is maximum possible
      function maxSum(arr, N) {
          // Stores the maximum sum and
          // respective K value
          let maxSum = -999999;
          let ans = -1;
 
          // Loop to iterate over all
          // value of K in range [1, N]
          for (let K = 1; K <= N; K++) {
              let sum = 0;
 
              // Iterating over all
              // multiples of K
              for (let i = K; i <= N; i += K) {
                  sum = sum + arr[i - 1];
              }
 
              // Update Maximum Sum
              if (sum > maxSum) {
                  maxSum = sum;
                  ans = K;
              }
          }
 
          // Return Answer
          return ans;
      }
 
      // Driver Code
 
      let arr = [-1, -2, -3];
      let N = arr.length;
 
      document.write(maxSum(arr, N));
 
 
// This code is contributed by Potta Lokesh
  </script>

2

 
 Complejidad temporal: O(N*log N)
Espacio auxiliar: O(1)