{"id":"9424bfb4-2b7b-4f79-bfe1-b3b5c9542e80","name":"Burst Balloons","description":"1. You are given an array(arr) of length N which represents N number of balloons.\r\n2. Each balloon is painted with a number on it.\r\n3. You have to collect maximum coins by bursting all the balloons.\r\n4. If you burst a balloon with index i, you will get (arr[i-1] * arr[i] * arr[i+1]) number of coins.\r\n5. If arr[i-1] and arr[i+1] don't exist, then you may assume their value as 1. ","inputFormat":"A number N\r\na1\r\na2.. N integers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 1000\r\n1 &lt;= arr[i] &lt;= 100","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[] arr) {\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 for (int i = 0; i < arr.length; i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n System.out.println(solution(arr));\r\n }\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"3\r\n1\r\n2\r\n3","sampleOutput":"12\r\n","questionVideo":"https://www.youtube.com/embed/YzvF8CqPafI?end=333","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":"1eede99b-b418-47d2-8295-554c10f4e1b1","name":"Burst Balloons","slug":"burst-balloons","type":1}],"next":{"id":"0a549d14-92fa-4367-a15a-aba43b13d725","name":"burst balloons MCQ","type":0,"slug":"burst-balloons-mcq"},"prev":{"id":"8ba04012-e901-4dd7-8e1d-6a52f98ec17d","name":"Circle and Chords","type":3,"slug":"circle-and-chords"}}}

Burst Balloons

1. You are given an array(arr) of length N which represents N number of balloons. 2. Each balloon is painted with a number on it. 3. You have to collect maximum coins by bursting all the balloons. 4. If you burst a balloon with index i, you will get (arr[i-1] * arr[i] * arr[i+1]) number of coins. 5. If arr[i-1] and arr[i+1] don't exist, then you may assume their value as 1.

{"id":"9424bfb4-2b7b-4f79-bfe1-b3b5c9542e80","name":"Burst Balloons","description":"1. You are given an array(arr) of length N which represents N number of balloons.\r\n2. Each balloon is painted with a number on it.\r\n3. You have to collect maximum coins by bursting all the balloons.\r\n4. If you burst a balloon with index i, you will get (arr[i-1] * arr[i] * arr[i+1]) number of coins.\r\n5. If arr[i-1] and arr[i+1] don't exist, then you may assume their value as 1. ","inputFormat":"A number N\r\na1\r\na2.. N integers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 1000\r\n1 &lt;= arr[i] &lt;= 100","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[] arr) {\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 for (int i = 0; i < arr.length; i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n System.out.println(solution(arr));\r\n }\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"3\r\n1\r\n2\r\n3","sampleOutput":"12\r\n","questionVideo":"https://www.youtube.com/embed/YzvF8CqPafI?end=333","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":"1eede99b-b418-47d2-8295-554c10f4e1b1","name":"Burst Balloons","slug":"burst-balloons","type":1}],"next":{"id":"0a549d14-92fa-4367-a15a-aba43b13d725","name":"burst balloons MCQ","type":0,"slug":"burst-balloons-mcq"},"prev":{"id":"8ba04012-e901-4dd7-8e1d-6a52f98ec17d","name":"Circle and Chords","type":3,"slug":"circle-and-chords"}}}
plane

Editor

Loading...

Burst Balloons

hard

1. You are given an array(arr) of length N which represents N number of balloons. 2. Each balloon is painted with a number on it. 3. You have to collect maximum coins by bursting all the balloons. 4. If you burst a balloon with index i, you will get (arr[i-1] * arr[i] * arr[i+1]) number of coins. 5. If arr[i-1] and arr[i+1] don't exist, then you may assume their value as 1.

Constraints

1 <= N <= 1000 1 <= arr[i] <= 100

Format

Input

A number N a1 a2.. N integers

Output

Check the sample output and question video.

Example

Sample Input

3 1 2 3

Sample Output

12

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode