Maximum subarray sum in an array created after repeated concatenation | Set | Java program for the above approach ; Function to find contiguous subarray with maximum sum if array is repeated K times ; Store the sum of the array arr [ ] ; Traverse the array and find sum ; Store the answer ; If K = 1 ; Apply Kadane algorithm to find sum ; Return the answer ; Stores the twice repeated array ; Traverse the range [ 0 , 2 * N ] ; Stores the maximum suffix sum ; Stores the maximum prefix sum ; Apply Kadane algorithm for 2 repetition of the array ; If the sum of the array is greater than 0 ; Return the answer ; Driver Code ; Given Input ; Function Call
import java . util . * ; class GFG { static int maxSubArraySumRepeated ( int [ ] arr , int N , int K ) { int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) sum += arr [ i ] ; int curr = arr [ 0 ] ; int ans = arr [ 0 ] ; if ( K == 1 ) { for ( int i = 1 ; i < N ; i ++ ) { curr = Math . max ( arr [ i ] , curr + arr [ i ] ) ; ans = Math . max ( ans , curr ) ; } return ans ; } ArrayList < Integer > V = new ArrayList < Integer > ( ) ; for ( int i = 0 ; i < 2 * N ; i ++ ) { V . add ( arr [ i % N ] ) ; } int maxSuf = V . get ( 0 ) ; int maxPref = V . get ( 2 * N - 1 ) ; curr = V . get ( 0 ) ; for ( int i = 1 ; i < 2 * N ; i ++ ) { curr += V . get ( i ) ; maxPref = Math . max ( maxPref , curr ) ; } curr = V . get ( 2 * N - 1 ) ; for ( int i = 2 * N - 2 ; i >= 0 ; i -- ) { curr += V . get ( i ) ; maxSuf = Math . max ( maxSuf , curr ) ; } curr = V . get ( 0 ) ; for ( int i = 1 ; i < 2 * N ; i ++ ) { curr = Math . max ( V . get ( i ) , curr + V . get ( i ) ) ; ans = Math . max ( ans , curr ) ; } if ( sum > 0 ) { int temp = sum * ( K - 2 ) ; ans = Math . max ( ans , Math . max ( temp + maxPref , temp + maxSuf ) ) ; } return ans ; } public static void main ( String args [ ] ) { int [ ] arr = { 10 , 20 , - 30 , - 1 , 40 } ; int N = arr . length ; int K = 10 ; System . out . print ( maxSubArraySumRepeated ( arr , N , K ) ) ; } }