Gegeben sei ein Array arr[] aus N Ganzzahlen und einer weiteren Ganzzahl K . Die Aufgabe besteht darin, die maximale Summe einer Teilfolge so zu finden, dass die Differenz der Indizes aller aufeinanderfolgenden Elemente in der Teilfolge im ursprünglichen Array genau K ist . Wenn beispielsweise arr[i] das erste Element der Teilsequenz ist, muss das nächste Element arr[i + k] sein, dann arr[i + 2k] und so weiter.
Beispiele: 
 

Eingabe: arr[] = {2, -3, -1, -1, 2}, K = 2 
Ausgabe: 3
Eingabe: arr[] = {2, 3, -1, -1, 2}, K = 3 
Ausgabe: 5 
 

Ansatz: Es sind K -Sequenzen möglich, bei denen die Elemente K voneinander entfernt sind, und diese können die Formen haben: 
 

0, 0 + k, 0 + 2k, …, 0 + n*k 
1, 1 + k, 1 + 2k, …, 1 + n*k 
2, 2 + k, 2 + 2k, …, 2 + n* k 
k-1, k-1 + k, k-1 + 2k, …, k-1 + n*k 
 



Nun ist jedes Subarray der Sequenzen eine Subsequenz des ursprünglichen Arrays, wobei die Elemente K voneinander entfernt sind.
Somit reduziert sich die Aufgabe nun darauf, die maximale Subarray-Summe dieser Sequenzen zu finden, die von Kadanes Algorithmus gefunden werden kann .
Unten ist die Implementierung des obigen Ansatzes: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum subarray sum
// for the array {a[i], a[i + k], a[i + 2k], ...}
int maxSubArraySum(int a[], int n, int k, int i)
{
    int max_so_far = INT_MIN, max_ending_here = 0;
 
    while (i < n) {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
 
        if (max_ending_here < 0)
            max_ending_here = 0;
 
        i += k;
    }
    return max_so_far;
}
 
// Function to return the sum of
// the maximum required subsequence
int find(int arr[], int n, int k)
{
    // To store the result
    int maxSum = 0;
 
    // Run a loop from 0 to k
    for (int i = 0; i <= min(n, k); i++) {
        int sum = 0;
 
        // Find the maximum subarray sum for the
        // array {a[i], a[i + k], a[i + 2k], ...}
        maxSum = max(maxSum,
                     maxSubArraySum(arr, n, k, i));
    }
 
    // Return the maximum value
    return maxSum;
}
 
// Driver code
int main()
{
    int arr[] = { 2, -3, -1, -1, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
 
    cout << find(arr, n, k);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the maximum subarray sum
// for the array {a[i], a[i + k], a[i + 2k], ...}
static int maxSubArraySum(int a[], int n,
                          int k, int i)
{
    int max_so_far = Integer.MIN_VALUE,
        max_ending_here = 0;
 
    while (i < n)
    {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
 
        if (max_ending_here < 0)
            max_ending_here = 0;
 
        i += k;
    }
    return max_so_far;
}
 
// Function to return the sum of
// the maximum required subsequence
static int find(int arr[], int n, int k)
{
    // To store the result
    int maxSum = 0;
 
    // Run a loop from 0 to k
    for (int i = 0; i <= Math.min(n, k); i++)
    {
        int sum = 0;
 
        // Find the maximum subarray sum for the
        // array {a[i], a[i + k], a[i + 2k], ...}
        maxSum = Math.max(maxSum,
                      maxSubArraySum(arr, n, k, i));
    }
 
    // Return the maximum value
    return maxSum;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = {2, -3, -1, -1, 2};
    int n = arr.length;
    int k = 2;
 
    System.out.println(find(arr, n, k));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 implementation of the approach
# Function to return the maximum subarray sum
# for the array {a[i], a[i + k], a[i + 2k], ...}
import sys
def maxSubArraySum(a, n, k, i):
 
    max_so_far = -sys.maxsize;
    max_ending_here = 0;
 
    while (i < n):
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here):
            max_so_far = max_ending_here;
 
        if (max_ending_here < 0):
            max_ending_here = 0;
 
        i += k;
     
    return max_so_far;
 
# Function to return the sum of
# the maximum required subsequence
def find(arr, n, k):
 
    # To store the result
    maxSum = 0;
 
    # Run a loop from 0 to k
    for i in range(0, min(n, k) + 1):
        sum = 0;
 
        # Find the maximum subarray sum for the
        # array {a[i], a[i + k], a[i + 2k], ...}
        maxSum = max(maxSum,
                     maxSubArraySum(arr, n, k, i));
     
    # Return the maximum value
    return maxSum;
 
# Driver code
if __name__ == '__main__':
    arr = [ 2, -3, -1, -1, 2 ];
    n = len(arr);
    k = 2;
 
    print(find(arr, n, k));
 
# This code is contributed by Princi Singh

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the maximum subarray sum
    // for the array {a[i], a[i + k], a[i + 2k], ...}
    static int maxSubArraySum(int []a, int n,
                              int k, int i)
    {
        int max_so_far = int.MinValue,
            max_ending_here = 0;
     
        while (i < n)
        {
            max_ending_here = max_ending_here + a[i];
            if (max_so_far < max_ending_here)
                max_so_far = max_ending_here;
     
            if (max_ending_here < 0)
                max_ending_here = 0;
     
            i += k;
        }
        return max_so_far;
    }
     
    // Function to return the sum of
    // the maximum required subsequence
    static int find(int []arr, int n, int k)
    {
        // To store the result
        int maxSum = 0;
     
        // Run a loop from 0 to k
        for (int i = 0; i <= Math.Min(n, k); i++)
        {
 
            // Find the maximum subarray sum for the
            // array {a[i], a[i + k], a[i + 2k], ...}
            maxSum = Math.Max(maxSum,
                              maxSubArraySum(arr, n, k, i));
        }
     
        // Return the maximum value
        return maxSum;
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = {2, -3, -1, -1, 2};
        int n = arr.Length;
        int k = 2;
     
        Console.WriteLine(find(arr, n, k));
    }   
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the maximum subarray sum
// for the array {a[i], a[i + k], a[i + 2k], ...}
function maxSubArraySum(a, n, k, i)
{
    let max_so_far = Number.MIN_VALUE,
        max_ending_here = 0;
 
    while (i < n) {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
 
        if (max_ending_here < 0)
            max_ending_here = 0;
 
        i += k;
    }
    return max_so_far;
}
 
// Function to return the sum of
// the maximum required subsequence
function find(arr, n, k)
{
    // To store the result
    let maxSum = 0;
 
    // Run a loop from 0 to k
    for (let i = 0; i <= Math.min(n, k); i++) {
        let sum = 0;
 
        // Find the maximum subarray sum for the
        // array {a[i], a[i + k], a[i + 2k], ...}
        maxSum = Math.max(maxSum,
                     maxSubArraySum(arr, n, k, i));
    }
 
    // Return the maximum value
    return maxSum;
}
 
// Driver code
    let arr = [ 2, -3, -1, -1, 2 ];
    let n = arr.length;
    let k = 2;
 
    document.write(find(arr, n, k));
 
</script>
Ausgabe: 
3

 

Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .