K Concatenation
medium
1. You are given an array(arr1) of integers and an integer k. 2. Another array(arr2) is formed by concatenating K copies of arr1. For example, if arr1 = {1,2} and k = 3, then arr2 = {1,2,1,2,1,2}. 3. You have to find the maximum subarray sum in arr2.
Constraints
1 <= N <= 10^5 1 <= K <= 10^5 -10^6 <= arr1[i] <= 10^6
Format
Input
A number N a1 a2.. N integers A number K
Output
A number representing maximum sum subarray in arr2.
Example
Sample Input
3
1
2
3
3
Sample Output
18
Question Video