Find maximum sum taking every Kth element in the array
Given an array arr[] of integers and an integer K, the task is to find the maximum sum taking every Kth element i.e. sum = arr[i] + arr[i + k] + arr[i + 2 * k] + arr[i + 3 * k] + ……. arr[i + q * k] starting with any i.
Examples:
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 = 10Input: arr[] = {3, 6, 4, 7, 2}, K = 2
Output: 13
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 <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> |
13
Time Complexity: O(N2) where N is the number of elements in array.
Auxiliary Space: O(1), no extra space required, so it is a constant.
Efficient Approach: This problem can be solved by using the concept of Suffix Arrays, we iterate the array from right side and store the suffix sum for each (i+k)’th element (ie., i+k < n) , and find the maximum sum. 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; // Initialize the sum array with zero int sum[n] = { 0 }; // Iterate from the right for ( int i = n - 1; i >= 0; i--) { // Update the sum starting at // the current element if (i + K < n) sum[i] = sum[i + K] + arr[i]; else sum[i] = arr[i]; // Update the maximum so far maximum = max(maximum, sum[i]); } 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; // Initialize the sum array with zero int [] sum = new int [n]; // Iterate from the right for ( int i = n - 1 ; i >= 0 ; i--) { // Update the sum starting at // the current element if (i + K < n) sum[i] = sum[i + K] + arr[i]; else sum[i] = arr[i]; // Update the maximum so far maximum = Math.max(maximum, sum[i]); } 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.print(maxSum(arr, n, K)); } } |
Python
# Python 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 def maxSum(arr, n, K): # Initialize the maximum with # the smallest value maximum = - 2 * * 32 ; # Initialize the sum array with zero sum = [ 0 ] * n # Iterate from the right for i in range (n - 1 , - 1 , - 1 ): # Update the sum starting at # the current element if ( i + K < n ): sum [i] = sum [i + K] + arr[i] else : sum [i] = arr[i]; # Update the maximum so far maximum = max ( maximum, sum [i] ) return maximum; # Driver code arr = [ 3 , 6 , 4 , 7 , 2 ] n = len (arr); K = 2 print (maxSum(arr, n, K)) |
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; // Initialize the sum array with zero int [] sum = new int [n]; // Iterate from the right for ( int i = n - 1; i >= 0; i--) { // Update the sum starting at // the current element if (i + K < n) sum[i] = sum[i + K] + arr[i]; else sum[i] = arr[i]; // Update the maximum so far maximum = Math.Max(maximum, sum[i]); } return maximum; } // Driver code public static void Main() { int [] arr = { 3, 6, 4, 7, 2 }; int n = arr.Length; int K = 2; Console.Write(maxSum(arr, n, K)); } } |
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; // Initialize the sum array with zero $sum = array ( $n ); // Iterate from the right for ( $i = $n - 1; $i >= 0; $i --) { // Update the sum starting at // the current element if ( $i + $K < $n ) $sum [ $i ] = $sum [ $i + $K ] + $arr [ $i ]; else $sum [ $i ] = $arr [ $i ]; // Update the maximum so far $maximum = max( $maximum , $sum [ $i ]); } 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 Learner_ |
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; // Initialize the sum array with zero var sum = Array(n).fill(0); // Iterate from the right for ( var i = n - 1; i >= 0; i--) { // Update the sum starting at // the current element if (i + K < n) sum[i] = sum[i + K] + arr[i]; else sum[i] = arr[i]; // Update the maximum so far maximum = Math.max(maximum, sum[i]); } 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> |
13
Time Complexity: O(N) where N is the number of elements in array.
Auxiliary Space: O(N), where N is the number of elements in array.