{"id":"d58548ca-88d5-4054-b9f4-23b1609f26f3","name":" K Concatenation","description":"1. You are given an array(arr1) of integers and an integer k.\r\n2. Another array(arr2) is formed by concatenating K copies of arr1.\r\n For example, if arr1 = {1,2} and k = 3, then arr2 = {1,2,1,2,1,2}.\r\n3. You have to find the maximum subarray sum in arr2.","inputFormat":"A number N\r\na1\r\na2.. N integers\r\nA number K","outputFormat":"A number representing maximum sum subarray in arr2.","constraints":"1 &lt;= N &lt;= 10^5\r\n1 &lt;= K &lt;= 10^5\r\n-10^6 &lt;= arr1[i] &lt;= 10^6 ","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static long solution(int[] arr, int k, long sum) {\r\n // write your code here\r\n\r\n return 0;\r\n }\r\n\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n long sum = 0;\r\n for (int i = 0; i < arr.length; i++) {\r\n arr[i] = scn.nextInt();\r\n sum += arr[i];\r\n }\r\n int k = scn.nextInt();\r\n System.out.println(solution(arr, k, sum));\r\n }\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"3\r\n1\r\n2\r\n3\r\n3","sampleOutput":"18\r\n","questionVideo":"https://www.youtube.com/embed/qnoOu5Usb4o?end=51","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"76a09b92-19d8-463d-ba89-289e91d2a88c","name":" K Concatenation","slug":"k-concatenation","type":1}],"next":{"id":"4e251771-fd08-4549-b5b3-fe899221d1d4","name":"K concatenation MCQ","type":0,"slug":"k-concatenation-mcq"},"prev":{"id":"e7ed24bb-d744-4600-b1d1-9a270bb2a951","name":"Kadane's Algorithm","type":3,"slug":"kadane-s-algorithm"}}}

K Concatenation

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.

{"id":"d58548ca-88d5-4054-b9f4-23b1609f26f3","name":" K Concatenation","description":"1. You are given an array(arr1) of integers and an integer k.\r\n2. Another array(arr2) is formed by concatenating K copies of arr1.\r\n For example, if arr1 = {1,2} and k = 3, then arr2 = {1,2,1,2,1,2}.\r\n3. You have to find the maximum subarray sum in arr2.","inputFormat":"A number N\r\na1\r\na2.. N integers\r\nA number K","outputFormat":"A number representing maximum sum subarray in arr2.","constraints":"1 &lt;= N &lt;= 10^5\r\n1 &lt;= K &lt;= 10^5\r\n-10^6 &lt;= arr1[i] &lt;= 10^6 ","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static long solution(int[] arr, int k, long sum) {\r\n // write your code here\r\n\r\n return 0;\r\n }\r\n\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n long sum = 0;\r\n for (int i = 0; i < arr.length; i++) {\r\n arr[i] = scn.nextInt();\r\n sum += arr[i];\r\n }\r\n int k = scn.nextInt();\r\n System.out.println(solution(arr, k, sum));\r\n }\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"3\r\n1\r\n2\r\n3\r\n3","sampleOutput":"18\r\n","questionVideo":"https://www.youtube.com/embed/qnoOu5Usb4o?end=51","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"76a09b92-19d8-463d-ba89-289e91d2a88c","name":" K Concatenation","slug":"k-concatenation","type":1}],"next":{"id":"4e251771-fd08-4549-b5b3-fe899221d1d4","name":"K concatenation MCQ","type":0,"slug":"k-concatenation-mcq"},"prev":{"id":"e7ed24bb-d744-4600-b1d1-9a270bb2a951","name":"Kadane's Algorithm","type":3,"slug":"kadane-s-algorithm"}}}
plane

Editor

Loading...

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

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode