Maximum subsequence sum obtained by concatenating disjoint subarrays whose lengths are prime | Python3 program for the above approach ; Function to return all prime numbers smaller than N ; Create a boolean array " prime [ 0 . . n ] " ; Initialize all its entries as true memset ( seive , true , sizeof ( seive ) ) ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p greater than or equal to the square of it ; Stores all prime numbers smaller than MAX ; Store all prime numbers ; If p is prime ; Function to build the auxiliary DP array from the start ; Base Case ; Stores all prime numbers < N ; Stores prefix sum ; Update prefix sum ; Iterate over range ; Update each state i . e . . when current element is excluded ; Find start & end index of subarrays when prime [ i ] is taken ; Check if starting point lies in the array ; Include the elements al al + 1 . . . ar ; Check if element lies before start of selected subarray ; Update value of dp [ i ] ; Function to find the maximum sum subsequence with prime length ; Auxiliary DP array ; Build DP array ; Print the result ; Driver Code ; Given arr [ ] ; Size of array ; Function Call
MAX = 100005 NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT seive = [ True for i in range ( MAX ) ] NEW_LINE for p in range ( 2 , MAX ) : NEW_LINE INDENT if p * p > MAX : NEW_LINE INDENT break NEW_LINE DEDENT if ( seive [ p ] == True ) : NEW_LINE INDENT for i in range ( p * p , MAX , p ) : NEW_LINE INDENT seive [ i ] = False NEW_LINE DEDENT DEDENT DEDENT v = [ ] NEW_LINE for p in range ( 2 , MAX ) : NEW_LINE INDENT if ( seive [ p ] ) : NEW_LINE INDENT v . append ( p ) NEW_LINE DEDENT DEDENT return v NEW_LINE DEDENT def build ( dp , arr , N ) : NEW_LINE INDENT dp [ 0 ] = 0 NEW_LINE dp [ 1 ] = 0 NEW_LINE prime = SieveOfEratosthenes ( ) NEW_LINE pref = [ 0 for i in range ( N + 1 ) ] NEW_LINE pref [ 0 ] = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT pref [ i ] = pref [ i - 1 ] + arr [ i - 1 ] NEW_LINE DEDENT for i in range ( 2 , N + 1 ) : NEW_LINE INDENT dp [ i ] = dp [ i - 1 ] NEW_LINE for j in range ( len ( prime ) + 1 ) : NEW_LINE INDENT r = i - 1 NEW_LINE l = r - prime [ j ] + 1 NEW_LINE if ( l < 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT temp = 0 NEW_LINE temp = pref [ r + 1 ] - pref [ l ] NEW_LINE if ( l - 2 >= 0 ) : NEW_LINE INDENT temp += dp [ l - 2 + 1 ] NEW_LINE DEDENT dp [ i ] = max ( dp [ i ] , temp ) NEW_LINE DEDENT DEDENT DEDENT def maxSumSubseq ( arr , N ) : NEW_LINE INDENT dp = [ 0 for i in range ( N + 1 ) ] NEW_LINE build ( dp , arr , N ) NEW_LINE print ( dp [ N ] ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 10 , 10 , 7 , 10 , 10 , 10 ] NEW_LINE N = len ( arr ) NEW_LINE maxSumSubseq ( arr , N ) NEW_LINE DEDENT