# Найдите максимальную сумму, взяв каждый 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 Kth element up to n, and find the maximum from all of these. The time complexity of this method will be O(N2)
Below is the implementation of the above approach:

## C++

 `// C++ implementation of the approach``#include ``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

 ``

## Javascript

 ``
Output:

`13`