{"id":"d475341b-312e-4e24-9340-b8e0a05cb066","name":"Rod Cutting","description":"1. You are given an integer N, which represents the length of a rod, and an array of integers, which represents the prices of rod pieces of length varying from 1 to \r\n N.\r\n2. You have to find the maximum value that can be obtained by selling the rod.\r\n3. You can sell it in pieces or as a whole.","inputFormat":"A number N\r\narr1\r\narr2.. N integers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 100000\r\n1 &lt;= arr[i] &lt;= 10^8","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static int solution(int[] prices) {\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[] prices = new int[n];\r\n for (int i = 0; i < n; i++) {\r\n prices[i] = scn.nextInt();\r\n }\r\n System.out.println(solution(prices));\r\n }\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"8\r\n1 \r\n5 \r\n8 \r\n9 \r\n10 \r\n17 \r\n17 \r\n20","sampleOutput":"22\r\n","questionVideo":"https://www.youtube.com/embed/eQuJb5gBkkc?end=148","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":"0f475e84-e81c-494e-9e3a-a29a5f69a123","name":"Rod Cutting","slug":"rod-cutting","type":1}],"next":{"id":"46b988d4-37e5-4412-ad86-ff0d4aceab76","name":"ROD CUTTING MCQ","type":0,"slug":"rod-cutting-mcq"},"prev":{"id":"962834e9-6824-43d9-84aa-82f8f9ef6295","name":"NUMBER OF PATHS ALONG THE EDGES IN UPPER HALF OF A SQUARE MATRIX MCQ","type":0,"slug":"number-of-paths-along-the-edges-in-upper-half-of-a-square-matrix-mcq"}}}

Rod Cutting

1. You are given an integer N, which represents the length of a rod, and an array of integers, which represents the prices of rod pieces of length varying from 1 to N. 2. You have to find the maximum value that can be obtained by selling the rod. 3. You can sell it in pieces or as a whole.

{"id":"d475341b-312e-4e24-9340-b8e0a05cb066","name":"Rod Cutting","description":"1. You are given an integer N, which represents the length of a rod, and an array of integers, which represents the prices of rod pieces of length varying from 1 to \r\n N.\r\n2. You have to find the maximum value that can be obtained by selling the rod.\r\n3. You can sell it in pieces or as a whole.","inputFormat":"A number N\r\narr1\r\narr2.. N integers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 100000\r\n1 &lt;= arr[i] &lt;= 10^8","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static int solution(int[] prices) {\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[] prices = new int[n];\r\n for (int i = 0; i < n; i++) {\r\n prices[i] = scn.nextInt();\r\n }\r\n System.out.println(solution(prices));\r\n }\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"8\r\n1 \r\n5 \r\n8 \r\n9 \r\n10 \r\n17 \r\n17 \r\n20","sampleOutput":"22\r\n","questionVideo":"https://www.youtube.com/embed/eQuJb5gBkkc?end=148","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":"0f475e84-e81c-494e-9e3a-a29a5f69a123","name":"Rod Cutting","slug":"rod-cutting","type":1}],"next":{"id":"46b988d4-37e5-4412-ad86-ff0d4aceab76","name":"ROD CUTTING MCQ","type":0,"slug":"rod-cutting-mcq"},"prev":{"id":"962834e9-6824-43d9-84aa-82f8f9ef6295","name":"NUMBER OF PATHS ALONG THE EDGES IN UPPER HALF OF A SQUARE MATRIX MCQ","type":0,"slug":"number-of-paths-along-the-edges-in-upper-half-of-a-square-matrix-mcq"}}}
plane

Editor


Loading...

Rod Cutting

easy

1. You are given an integer N, which represents the length of a rod, and an array of integers, which represents the prices of rod pieces of length varying from 1 to N. 2. You have to find the maximum value that can be obtained by selling the rod. 3. You can sell it in pieces or as a whole.

Constraints

1 <= N <= 100000 1 <= arr[i] <= 10^8

Format

Input

A number N arr1 arr2.. N integers

Output

Check the sample output and question video.

Example

Sample Input

8 1 5 8 9 10 17 17 20

Sample Output

22

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode