Last Updated: 1 Dec, 2021
Maximum Sum of Zigzag Pattern
Moderate
Asked in companies
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].
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
Approaches
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’).
- If ARR[i] <ARR[N]:
- Return ‘ANS’.
- If N is equal to 0:
- 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’).
- If ARR[i] > ARR[N]:
- Return ‘ANS’.
- If N is equal to 0:
- 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’.
In this approach, we will use the same recursive functions, we used in approach 1 but we will use memoization to reduce the complexity as the answer for each value will be calculated only once.
We will define two arrays ‘INC_DP’ and ‘DEC_DP’ to store the answers.
Algorithm:
- Defining INC(‘N’,’ARR’, INC_DP, DEC_DP) function:
- If N is equal to 0:
- Return ARR[0].
- If INC_DP[N] is not equal to -1:
- Return INC_DP[N].
- 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’, INC_DP, DEC_DP).
- If ARR[i] <ARR[N]:
- Set INC_DP[N] as ‘ANS’.
- Return ‘ANS’.
- If N is equal to 0:
- Defining DEC(‘N’,’ARR’, INC_DP, DEC_DP) function:
- If N is equal to 0:
- Return ARR[0].
- If DEC_DP[N] is not equal to -1:
- Return DEC_DP[N].
- 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’, INC_DP, DEC_DP).
- If ARR[i] >ARR[N]:
- Set DEC_DP[N] as ‘ANS’.
- Return ‘ANS’.
- If N is equal to 0:
- Declare two arrays of size N, INC_DP and DEC_DP.
- Set all values of both the arrays with -1.
- Set ‘ANS’ as 0.
- For i in range 0 to ‘N’-1:
- Set ‘ANS’ as the maximum of ‘ANS’ and INC(i,ARR, INC_DP, DEC_DP).
- Set ‘ANS’ as the maximum of ‘ANS’ and DEC(i,ARR, INC_DP, DEC_DP).
- Return ‘ANS’.
In this approach, we will use dynamic programming and find the answer to the problem. We will prepare two arrays, INC[] and DEC[], to find the maximum required sum.
INC[i] will store the maximum sum if the last element of the subsequence is i’th element and the last value is greater than the previous.
DEC[i] will store the maximum sum if the last element of the subsequence is i’th element and the last value is less than the previous.
Now, we will compute the values by iterating the array using a nested loop as :
If ‘ARR[i]’ > ‘ARR’[j]: Set ‘DEC[i]’ as maximum of DEC[i] and (ARR[i]+INC[j]) as we can include the ith element.
If ‘ARR[i]’ < ARR[j]: Set ‘INC[i]’ as maximum of INC[i] and (ARR[i]+DEC[j]) as we can include the ith element.
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:
- Define two arrays ‘INC’ and ‘DEC’ of size ‘N’, and set all values as 0.
- Set ‘INC[0]’ as ARR[0].
- Set ‘DEC[0]’ as ARR[0]
- For i in range 1 to ‘N’-1:
- For j in range 0 to i-1:
- If ‘ARR[i]’ < ARR[j]:
- Set DEC[i] as maximum of DEC[i] and (ARR[i]+INC[j]).
- If ‘ARR[i]’ > ARR[j] :
- Set ‘INC[i]’ as maximum of INC[i] and (ARR[i]+DEC[j])
- If ‘ARR[i]’ < ARR[j]:
- For j in range 0 to i-1:
- All value of INC and DEC is computed.
- Set ‘ANS’ as 0.
- For i in range 0 to ‘N’-1:
- Set ‘ANS’ as the maximum of ‘ANS’ and ‘INC[i]’.
- Set ‘ANS’ as the maximum of ‘ANS’ and ‘DEC[i]’.
- Return ‘ANS’.
Similar problems