{"id":"a7d334d9-5df3-4b3d-a086-b311030ce38c","name":"Alternating Subsequence With Maximum Sum","description":"1. You are given an array(arr) of integers.\r\n2. You have to find the alternating subsequence wit maximum sum.\r\n3. The alternating subsequence should start with the first element of the array.\r\n4. The first step in alternating subsequence should be decreasing, then increasing, then decreasing and so on.\r\n\r\nNote -> If the array contains only one element, then your answer should be that element itself.","inputFormat":"A number N\r\narr1\r\narr2... N integers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 10^4\r\n1 &lt;= arr[i] &lt;= 10^4","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\t\r\n\tpublic static int solution(int[] arr) {\r\n\t\t// write your code here\r\n\r\n\t\treturn 0;\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 < n; i++){\r\n\t\t\tarr[i] = scn.nextInt();\r\n\t\t}\r\n\t\tSystem.out.println(solution(arr));\r\n\t}\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"6\r\n5 3 2 5 2 1","sampleOutput":"15\r\n","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":"4b26bb1d-60d1-4687-bf09-f25d7aeac509","name":"Alternating Subsequence With Maximum Sum","slug":"alternating-subsequence-with-maximum-sum","type":1}],"next":{"id":"c9f7599f-03ee-4047-8f5a-d272afab2554","name":"Minimum Insertions To Make Palindrome","type":1,"slug":"minimum-insertions-to-make-palindrome"},"prev":{"id":"3083a439-4154-4843-aa37-6a4550f9394d","name":"Temple Offerings","type":1,"slug":"temple-offerings"}}}

Alternating Subsequence With Maximum Sum

1. You are given an array(arr) of integers. 2. You have to find the alternating subsequence wit maximum sum. 3. The alternating subsequence should start with the first element of the array. 4. The first step in alternating subsequence should be decreasing, then increasing, then decreasing and so on. Note -> If the array contains only one element, then your answer should be that element itself.

{"id":"a7d334d9-5df3-4b3d-a086-b311030ce38c","name":"Alternating Subsequence With Maximum Sum","description":"1. You are given an array(arr) of integers.\r\n2. You have to find the alternating subsequence wit maximum sum.\r\n3. The alternating subsequence should start with the first element of the array.\r\n4. The first step in alternating subsequence should be decreasing, then increasing, then decreasing and so on.\r\n\r\nNote -> If the array contains only one element, then your answer should be that element itself.","inputFormat":"A number N\r\narr1\r\narr2... N integers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 10^4\r\n1 &lt;= arr[i] &lt;= 10^4","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\t\r\n\tpublic static int solution(int[] arr) {\r\n\t\t// write your code here\r\n\r\n\t\treturn 0;\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 < n; i++){\r\n\t\t\tarr[i] = scn.nextInt();\r\n\t\t}\r\n\t\tSystem.out.println(solution(arr));\r\n\t}\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"6\r\n5 3 2 5 2 1","sampleOutput":"15\r\n","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":"4b26bb1d-60d1-4687-bf09-f25d7aeac509","name":"Alternating Subsequence With Maximum Sum","slug":"alternating-subsequence-with-maximum-sum","type":1}],"next":{"id":"c9f7599f-03ee-4047-8f5a-d272afab2554","name":"Minimum Insertions To Make Palindrome","type":1,"slug":"minimum-insertions-to-make-palindrome"},"prev":{"id":"3083a439-4154-4843-aa37-6a4550f9394d","name":"Temple Offerings","type":1,"slug":"temple-offerings"}}}
plane

Editor


Loading...

Alternating Subsequence With Maximum Sum

medium

1. You are given an array(arr) of integers. 2. You have to find the alternating subsequence wit maximum sum. 3. The alternating subsequence should start with the first element of the array. 4. The first step in alternating subsequence should be decreasing, then increasing, then decreasing and so on. Note -> If the array contains only one element, then your answer should be that element itself.

Constraints

1 <= N <= 10^4 1 <= arr[i] <= 10^4

Format

Input

A number N arr1 arr2... N integers

Output

Check the sample output and question video.

Example

Sample Input

6 5 3 2 5 2 1

Sample Output

15

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode