{"id":"27dc80e8-c470-4484-b673-d1d8ab271346","name":"Maximum Sum Of Three Non-overlapping Subarrays ","description":"1. You are given an array(arr) of positive numbers and a number K.\r\n2. You have to find the maximum sum of elements in three non-overlapping subarrays.\r\n3. Also, you have to print indices representing the starting position of every subarray.\r\n4. If there are multiple answers, print the lexicographically smallest one.","inputFormat":"A number N\r\narr1\r\narr2.. N numbers\r\nA number K","outputFormat":"4 space-separated numbers, where first number represents the maximum sum of three non-overlapping subarrays and rest three represents the starting position of every subarray.","constraints":"1 &lt;= N &lt;= 20000\r\n1 &lt;= arr[i] &lt;= 10^5\r\n1 &lt;= K &lt;= N/3","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n\tpublic static void solution(int[] arr, int k){\r\n\t\t// write your code here\r\n\t\t\r\n\t}\r\n\t\r\n\tpublic static void main(String[] args) {\r\n\t\tScanner scn = new Scanner(System.in);\r\n\t\tint n = scn.nextInt();\r\n\t\tint[] arr = new int[n];\r\n\t\tfor(int i = 0 ; i < arr.length; i++){\r\n\t\t\tarr[i] = scn.nextInt();\r\n\t\t}\r\n\t\tint k = scn.nextInt();\r\n\t\tsolution(arr,k);\r\n\t}\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"8\r\n1 2 1 2 6 7 5 1 \r\n2\r\n","sampleOutput":"23 0 3 5 ","questionVideo":"","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":"6e65ed40-c376-41ca-a262-40b5a241da7e","name":"Maximum Sum Of Three Non-overlapping Subarrays ","slug":"maximum-sum-of-three-non-overlapping-subarrays","type":1}],"next":{"id":"233c3844-e199-4b36-a418-8d89afbc3136","name":"Maximum Sum Of M Non-overlapping Subarrays","type":1,"slug":"maximum-sum-of-m-non-overlapping-subarrays"},"prev":{"id":"fbc7716d-e773-45cc-8ec7-984c2e02b22e","name":"Maximum Sum Of Two Non-overlapping Subarrays","type":3,"slug":"maximum-sum-of-two-non-overlapping-subarrays"}}}

Maximum Sum Of Three Non-overlapping Subarrays

1. You are given an array(arr) of positive numbers and a number K. 2. You have to find the maximum sum of elements in three non-overlapping subarrays. 3. Also, you have to print indices representing the starting position of every subarray. 4. If there are multiple answers, print the lexicographically smallest one.

{"id":"27dc80e8-c470-4484-b673-d1d8ab271346","name":"Maximum Sum Of Three Non-overlapping Subarrays ","description":"1. You are given an array(arr) of positive numbers and a number K.\r\n2. You have to find the maximum sum of elements in three non-overlapping subarrays.\r\n3. Also, you have to print indices representing the starting position of every subarray.\r\n4. If there are multiple answers, print the lexicographically smallest one.","inputFormat":"A number N\r\narr1\r\narr2.. N numbers\r\nA number K","outputFormat":"4 space-separated numbers, where first number represents the maximum sum of three non-overlapping subarrays and rest three represents the starting position of every subarray.","constraints":"1 &lt;= N &lt;= 20000\r\n1 &lt;= arr[i] &lt;= 10^5\r\n1 &lt;= K &lt;= N/3","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n\tpublic static void solution(int[] arr, int k){\r\n\t\t// write your code here\r\n\t\t\r\n\t}\r\n\t\r\n\tpublic static void main(String[] args) {\r\n\t\tScanner scn = new Scanner(System.in);\r\n\t\tint n = scn.nextInt();\r\n\t\tint[] arr = new int[n];\r\n\t\tfor(int i = 0 ; i < arr.length; i++){\r\n\t\t\tarr[i] = scn.nextInt();\r\n\t\t}\r\n\t\tint k = scn.nextInt();\r\n\t\tsolution(arr,k);\r\n\t}\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"8\r\n1 2 1 2 6 7 5 1 \r\n2\r\n","sampleOutput":"23 0 3 5 ","questionVideo":"","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":"6e65ed40-c376-41ca-a262-40b5a241da7e","name":"Maximum Sum Of Three Non-overlapping Subarrays ","slug":"maximum-sum-of-three-non-overlapping-subarrays","type":1}],"next":{"id":"233c3844-e199-4b36-a418-8d89afbc3136","name":"Maximum Sum Of M Non-overlapping Subarrays","type":1,"slug":"maximum-sum-of-m-non-overlapping-subarrays"},"prev":{"id":"fbc7716d-e773-45cc-8ec7-984c2e02b22e","name":"Maximum Sum Of Two Non-overlapping Subarrays","type":3,"slug":"maximum-sum-of-two-non-overlapping-subarrays"}}}
plane

Editor


Loading...

Maximum Sum Of Three Non-overlapping Subarrays

hard

1. You are given an array(arr) of positive numbers and a number K. 2. You have to find the maximum sum of elements in three non-overlapping subarrays. 3. Also, you have to print indices representing the starting position of every subarray. 4. If there are multiple answers, print the lexicographically smallest one.

Constraints

1 <= N <= 20000 1 <= arr[i] <= 10^5 1 <= K <= N/3

Format

Input

A number N arr1 arr2.. N numbers A number K

Output

4 space-separated numbers, where first number represents the maximum sum of three non-overlapping subarrays and rest three represents the starting position of every subarray.

Example

Sample Input

8 1 2 1 2 6 7 5 1 2

Sample Output

23 0 3 5

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode