Maximum subarray sum in an array created after repeated concatenation | Set | 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 ; Given Input ; Function Call
function maxSubArraySumRepeated ( arr , N , K ) { let sum = 0 ; for ( let i = 0 ; i < N ; i ++ ) sum += arr [ i ] ; let curr = arr [ 0 ] ; let ans = arr [ 0 ] ; if ( K == 1 ) { for ( let i = 1 ; i < N ; i ++ ) { curr = Math . max ( arr [ i ] , curr + arr [ i ] ) ; ans = Math . max ( ans , curr ) ; } return ans ; } let V = [ ] ; for ( let i = 0 ; i < 2 * N ; i ++ ) { V . push ( arr [ i % N ] ) ; } let maxSuf = V [ 0 ] ; let maxPref = V [ 2 * N - 1 ] ; curr = V [ 0 ] ; for ( let i = 1 ; i < 2 * N ; i ++ ) { curr += V [ i ] ; maxPref = Math . max ( maxPref , curr ) ; } curr = V [ 2 * N - 1 ] ; for ( let i = 2 * N - 2 ; i >= 0 ; i -- ) { curr += V [ i ] ; maxSuf = Math . max ( maxSuf , curr ) ; } curr = V [ 0 ] ; for ( let i = 1 ; i < 2 * N ; i ++ ) { curr = Math . max ( V [ i ] , curr + V [ i ] ) ; ans = Math . max ( ans , curr ) ; } if ( sum > 0 ) { let temp = sum * ( K - 2 ) ; ans = Math . max ( ans , Math . max ( temp + maxPref , temp + maxSuf ) ) ; } return ans ; } let arr = [ 10 , 20 , - 30 , - 1 , 40 ] ; let N = arr . length ; let K = 10 ; document . write ( maxSubArraySumRepeated ( arr , N , K ) ) ;