Найдите максимальную сумму, взяв каждый K-й элемент в массиве

Опубликовано: 14 Января, 2022

Учитывая массив целых чисел arr [] и целое число K , задача состоит в том, чтобы найти максимальную сумму, взяв каждый K- ^й элемент, т.е. sum = arr [i] + arr [i + k] + arr [i + 2 * k] + arr [i + 3 * k] + ……. arr [i + q * k], начиная с любого i .
Примеры:

Input: arr[] = {3, -5, 6, 3, 10}, K = 3
Output: 10
All possible sequence are:
3 + 3 = 6
-5 + 10 = 5
6 = 6
3 = 3
10 = 10
Input: arr[] = {3, 6, 4, 7, 2}, K = 2
Output: 13

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Naive Approach: The idea to solve this by using two nested loops and find the sum of every sequence starting from index i and sum every K^th element up to n, and find the maximum from all of these. The time complexity of this method will be O(N²)
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
int maxSum(int arr[], int n, int K)
{
 
    // Initialize the maximum with
    // the smallest value
    int maximum = INT_MIN;
 
    // Find maximum from all sequences
    for (int i = 0; i < n; i++) {
 
        int sumk = 0;
 
        // Sum of the sequence
        // starting from index i
        for (int j = i; j < n; j += K)
            sumk = sumk + arr[j];
 
        // Update maximum
        maximum = max(maximum, sumk);
    }
 
    return maximum;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 6, 4, 7, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
 
    cout << maxSum(arr, n, K);
 
    return (0);
}

Java

// Java implementation of the approach
class GFG
{
     
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
static int maxSum(int arr[], int n, int K)
{
 
    // Initialize the maximum with
    // the smallest value
    int maximum = Integer.MIN_VALUE;
 
    // Find maximum from all sequences
    for (int i = 0; i < n; i++)
    {
 
        int sumk = 0;
 
        // Sum of the sequence
        // starting from index i
        for (int j = i; j < n; j += K)
            sumk = sumk + arr[j];
 
        // Update maximum
        maximum = Math.max(maximum, sumk);
    }
 
    return maximum;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 6, 4, 7, 2 };
    int n = arr.length;
    int K = 2;
 
    System.out.println(maxSum(arr, n, K));
}
}
 
// This code is contributed by Code_Mech

Python3

# Python 3 implementation of the approach
import sys
 
# Function to return the maximum sum for
# every possible sequence such that
# a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
# is maximized
def maxSum(arr, n, K):
     
    # Initialize the maximum with
    # the smallest value
    maximum = -sys.maxsize - 1
 
    # Find maximum from all sequences
    for i in range(n):
        sumk = 0
 
        # Sum of the sequence
        # starting from index i
        for j in range(i, n, K):
            sumk = sumk + arr[j]
 
        # Update maximum
        maximum = max(maximum, sumk)
 
    return maximum
 
# Driver code
if __name__ == "__main__":
    arr = [3, 6, 4, 7, 2]
    n = len(arr)
    K = 2
    print(maxSum(arr, n, K))
     
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
static int maxSum(int []arr, int n, int K)
{
 
    // Initialize the maximum with
    // the smallest value
    int maximum = int.MinValue;
 
    // Find maximum from all sequences
    for (int i = 0; i < n; i++)
    {
 
        int sumk = 0;
 
        // Sum of the sequence
        // starting from index i
        for (int j = i; j < n; j += K)
            sumk = sumk + arr[j];
 
        // Update maximum
        maximum = Math.Max(maximum, sumk);
    }
 
    return maximum;
}
 
// Driver code
public static void Main()
{
    int []arr = { 3, 6, 4, 7, 2 };
    int n = arr.Length;
    int K = 2;
 
    Console.WriteLine(maxSum(arr, n, K));
}
}
 
// This code is contributed by Akanksha Rai

PHP

<?php
// PHP implementation of the approach
 
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
function maxSum($arr, $n, $K)
{
 
    // Initialize the maximum with
    // the smallest value
    $maximum = PHP_INT_MIN;
 
    // Find maximum from all sequences
    for ($i = 0; $i < $n; $i++)
    {
        $sumk = 0;
 
        // Sum of the sequence
        // starting from index i
        for ($j = $i; $j < $n; $j += $K)
            $sumk = $sumk + $arr[$j];
 
        // Update maximum
        $maximum = max($maximum, $sumk);
    }
 
    return $maximum;
}
 
// Driver code
$arr = array(3, 6, 4, 7, 2);
$n = sizeof($arr);
$K = 2;
 
echo maxSum($arr, $n, $K);
 
// This code is contributed by Akanksha Rai
?>

Javascript

<script>
 
 
// JavaScript implementation of the approach
 
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
function maxSum(arr, n, K)
{
 
    // Initialize the maximum with
    // the smallest value
    var maximum = -1000000000;
 
    // Find maximum from all sequences
    for (var i = 0; i < n; i++) {
 
        var sumk = 0;
 
        // Sum of the sequence
        // starting from index i
        for (var j = i; j < n; j += K)
            sumk = sumk + arr[j];
 
        // Update maximum
        maximum = Math.max(maximum, sumk);
    }
 
    return maximum;
}
 
// Driver code
var arr = [3, 6, 4, 7, 2];
var n = arr.length;
var K = 2;
document.write( maxSum(arr, n, K));
 
 
</script>

Output:

Алгоритмы Java

Найдите максимальную сумму, взяв каждый K-й элемент в массиве

C++

Java

Python3

C#

PHP

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ