Maximum Sum of Zigzag Pattern

Moderate
0/80
Average time to solve is 25m
3 upvotes
Asked in companies
Flipkart limitedGoogle inc

Problem statement

Ninja loves zigzag pattern. So, looking at an array ‘ARR’ having N elements, Ninja is interested to find the maximum sum of the zigzag subsequence pattern?

A Zigzag subsequence is defined as the subsequence that starts from the first element, then a strictly decreasing element, then strictly increasing element, and then strictly decreasing, and so on. Or starts with the first element, then a strictly increasing element, then a strictly decreasing element, and so on.

Can you help Ninja to solve this problem?

For Example 
If the ARR is [4,3,11,12,2] ,the zigzag subsequence having maximum sum is [4,3,12,2].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, ‘N’, denoting the number of elements in array ‘ARR’.

The following line contains ‘N’ values corresponding to elements of ‘ARR’.
Output Format: 
For each test case, print the maximum sum of the zigzag subsequence.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 1000.
1 <=ARR[i] <=10^5.

Time limit: 1 sec
Sample Input 1:
2
5 
4 3 11 12 2
5 
4 5 2 2 4
Sample Output 1:
21
15
Explanation of sample input 1:
For the first test case,

The zigzag subsequence having a maximum sum is [4,3,12,2], the sum of the subsequence is 21. Hence, the answer is 21.

For the second test case:

The zigzag subsequence having a maximum sum is [4,5,2,4], the sum of the subsequence is 15. Hence, the answer is 15.
Sample Input 2:
2
5
2 1 6 3 3 
6
1 7 1 8 2 9
Sample Output 2:
12
28
Hint

Find the answer till the ith element.

Approaches (3)
Recursion

In this approach, we will use recursion and find the answer to the problem. We will define two functions INC(n) and DEC(n).

INC(n) will return the maximum sum if the last element of the subsequence is n’th element and the last value is greater than the previous. 

DEC(n) will return the maximum sum if the last element of the subsequence is n’th element and the last value is less than the previous. 

Now, we will compute the values using recursion we will iterate through 0 to ‘N’-1th index and find the index for which the sum is maximum.

In the end, we will iterate the whole array and find the maximum value of INC(i) and DEC(i), and return the maximum sum value.


 

Algorithm:

 

  • Defining INC(‘N’,’ARR’) function:
    • If N is equal to 0:
      • Return ARR[0].
    • Set ‘ANS’ as 0.
    • For i in range 0 to N-1, do the following:
      • If ARR[i] <ARR[N]:
        • Set ANS as the maximum of ‘ANS’ and ARR[n] + DEC(i,’ARR’).
    • Return ‘ANS’.
  • Defining DEC(‘N’,’ARR’) function:
    • If N is equal to 0:
      • Return ARR[0].
    • Set ‘ANS’ as 0.
    • For i in range 0 to N-1, do the following:
      • If ARR[i]  > ARR[N]:
        • Set ANS as the maximum of ‘ANS’ and ARR[n] + INC(i,’ARR’).
    • Return ‘ANS’.

 

  • Set ‘ANS’ as 0.
  • For i in range 0 to ‘N’-1:
    • Set ‘ANS’ as the maximum of ‘ANS’ and INC(i,ARR).
    • Set ‘ANS’ as the maximum of ‘ANS’ and DEC(i,ARR).
  • Return ‘ANS’.
Time Complexity

O(N^N), where ‘N’ is the number of elements in array ‘ARR’.

 

In this approach, we use recursive functions and each recursive function is making N more function calls. So the total number of function calls will be N^N. Hence, the overall time complexity is O(N^N).

Space Complexity

O(N), where ‘N’ is the number of elements in array ‘ARR’.

 

In this approach, we are using recursive functions, so a total space of N will be used for the memory stack. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Maximum Sum of Zigzag Pattern
Full screen
Console