Maximum subsequence sum obtained by concatenating disjoint subarrays whose lengths are prime | Java 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 ; Driver Code ; Given arr [ ] ; Size of array ; Function Call
import java . util . * ; class GFG { static int MAX = 100005 ; static Vector < Integer > SieveOfEratosthenes ( ) { boolean [ ] seive = new boolean [ MAX ] ; Arrays . fill ( seive , true ) ; for ( int p = 2 ; p * p < MAX ; p ++ ) { if ( seive [ p ] == true ) { for ( int i = p * p ; i < MAX ; i += p ) { seive [ i ] = false ; } } } Vector < Integer > v = new Vector < Integer > ( ) ; for ( int p = 2 ; p < MAX ; p ++ ) { if ( seive [ p ] ) { v . add ( p ) ; } } return v ; } static void build ( int dp [ ] , int arr [ ] , int N ) { dp [ 0 ] = 0 ; dp [ 1 ] = 0 ; Vector < Integer > prime = SieveOfEratosthenes ( ) ; int [ ] pref = new int [ N + 1 ] ; pref [ 0 ] = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { pref [ i ] = pref [ i - 1 ] + arr [ i - 1 ] ; } for ( int i = 2 ; i <= N ; i ++ ) { dp [ i ] = dp [ i - 1 ] ; for ( int j = 0 ; j <= prime . size ( ) ; j ++ ) { int r = i - 1 ; int l = r - prime . get ( j ) + 1 ; if ( l < 0 ) break ; int temp = 0 ; temp = pref [ r + 1 ] - pref [ l ] ; if ( l - 2 >= 0 ) temp += dp [ l - 2 + 1 ] ; dp [ i ] = Math . max ( dp [ i ] , temp ) ; } } } static void maxSumSubseq ( int arr [ ] , int N ) { int [ ] dp = new int [ N + 1 ] ; build ( dp , arr , N ) ; System . out . print ( dp [ N ] ) ; } public static void main ( String args [ ] ) { int arr [ ] = { 10 , 10 , 7 , 10 , 10 , 10 } ; int N = arr . length ; maxSumSubseq ( arr , N ) ; } }