Maximum subsequence sum obtained by concatenating disjoint subarrays whose lengths are prime | Javascript 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 ; 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 ; Given arr [ ] ; Size of array ; Function Call
let MAX = 100005 function SieveOfEratosthenes ( ) { let seive = new Array ( MAX ) ; seive . fill ( true ) for ( let p = 2 ; p * p < MAX ; p ++ ) { if ( seive [ p ] == true ) { for ( let i = p * p ; i < MAX ; i += p ) { seive [ i ] = false ; } } } let v = new Array ( ) ; for ( let p = 2 ; p < MAX ; p ++ ) { if ( seive [ p ] ) { v . push ( p ) ; } } return v ; } function build ( dp , arr , N ) { dp [ 0 ] = 0 ; dp [ 1 ] = 0 ; let prime = SieveOfEratosthenes ( ) ; let pref = new Array ( N + 1 ) ; pref [ 0 ] = 0 ; for ( let i = 1 ; i <= N ; i ++ ) { pref [ i ] = pref [ i - 1 ] + arr [ i - 1 ] ; } for ( let i = 2 ; i <= N ; i ++ ) { dp [ i ] = dp [ i - 1 ] ; for ( let j = 0 ; j <= prime . length ; j ++ ) { let r = i - 1 ; let l = r - prime [ j ] + 1 ; if ( l < 0 ) break ; let temp = 0 ; temp = pref [ r + 1 ] - pref [ l ] ; if ( l - 2 >= 0 ) temp += dp [ l - 2 + 1 ] ; dp [ i ] = Math . max ( dp [ i ] , temp ) ; } } } function maxSumSubseq ( arr , N ) { let dp = new Array ( N + 1 ) ; build ( dp , arr , N ) ; document . write ( dp [ N ] ) ; } let arr = [ 10 , 10 , 7 , 10 , 10 , 10 ] ; let N = arr . length ; maxSumSubseq ( arr , N ) ;