Maximum subsequence sum such that all elements are K distance apart | Function to return the maximum subarray sum for the array { a [ i ] , a [ i + k ] , a [ i + 2 k ] , ... } ; Function to return the sum of the maximum required subsequence ; To store the result ; Run a loop from 0 to k ; Find the maximum subarray sum for the array { a [ i ] , a [ i + k ] , a [ i + 2 k ] , ... } ; Return the maximum value ; Driver code
import sys NEW_LINE def maxSubArraySum ( a , n , k , i ) : NEW_LINE INDENT max_so_far = - sys . maxsize ; NEW_LINE max_ending_here = 0 ; NEW_LINE while ( i < n ) : NEW_LINE INDENT max_ending_here = max_ending_here + a [ i ] ; NEW_LINE if ( max_so_far < max_ending_here ) : NEW_LINE INDENT max_so_far = max_ending_here ; NEW_LINE DEDENT if ( max_ending_here < 0 ) : NEW_LINE INDENT max_ending_here = 0 ; NEW_LINE DEDENT i += k ; NEW_LINE DEDENT return max_so_far ; NEW_LINE DEDENT def find ( arr , n , k ) : NEW_LINE INDENT maxSum = 0 ; NEW_LINE for i in range ( 0 , min ( n , k ) + 1 ) : NEW_LINE INDENT sum = 0 ; NEW_LINE maxSum = max ( maxSum , maxSubArraySum ( arr , n , k , i ) ) ; NEW_LINE DEDENT return maxSum ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , - 3 , - 1 , - 1 , 2 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE k = 2 ; NEW_LINE print ( find ( arr , n , k ) ) ; NEW_LINE DEDENT