Maximum sum of K | Java Program to implement the above approach ; Function to print the sum of subarray of length K having maximum distinct prime factors ; If K exceeds N ; Stores the count of distinct primes ; True , if index ' i ' is a prime ; Initialize the count of factors to 0 and set all indices as prime ; If i is prime ; Number is prime ; Count of factors of a prime number is 1 ; Increment CountDistinct as the factors of i ; Mark its multiple non - prime ; Compute sum of first K - length subarray ; Compute sums of remaining windows by removing first element of the previous window and adding last element of the current window ; Print the maximum sum ; Driver Code ; Given array ; Given size of subarray ; Size of the array
import java . io . * ; import java . util . * ; class GFG { static int MAX = 100001 ; static void maxSum ( int arr [ ] , int N , int K ) { if ( N < K ) { System . out . println ( " Invalid " ) ; return ; } int CountDistinct [ ] = new int [ MAX + 1 ] ; boolean prime [ ] = new boolean [ MAX + 1 ] ; for ( int i = 0 ; i <= MAX ; i ++ ) { CountDistinct [ i ] = 0 ; prime [ i ] = true ; } for ( int i = 2 ; i <= MAX ; i ++ ) { if ( prime [ i ] == true ) { CountDistinct [ i ] = 1 ; for ( int j = i * 2 ; j <= MAX ; j += i ) { CountDistinct [ j ] ++ ; prime [ j ] = false ; } } } int Maxarr_sum = 0 , DistPrimeSum = 0 ; for ( int i = 0 ; i < K ; i ++ ) { Maxarr_sum += arr [ i ] ; DistPrimeSum += CountDistinct [ arr [ i ] ] ; } int curr_sum = DistPrimeSum ; int curr_arrSum = Maxarr_sum ; for ( int i = K ; i < N ; i ++ ) { curr_sum += CountDistinct [ arr [ i ] ] - CountDistinct [ arr [ i - K ] ] ; curr_arrSum += arr [ i ] - arr [ i - K ] ; if ( curr_sum > DistPrimeSum ) { DistPrimeSum = curr_sum ; Maxarr_sum = curr_arrSum ; } else if ( curr_sum == DistPrimeSum ) { Maxarr_sum = Math . max ( curr_arrSum , Maxarr_sum ) ; } } System . out . println ( Maxarr_sum ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 4 , 2 , 10 , 3 } ; int K = 3 ; int N = arr . length ; maxSum ( arr , N , K ) ; } }