Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
3.
Problem example
4.
Brute Force Approach
4.1.
Algorithm
4.2.
Implementation
4.2.1.
Algorithm Complexity: 
5.
Efficient Approach
5.1.
Algorithm 
5.2.
Implementation
5.2.1.
Algorithm Complexity: 
6.
Frequently Asked Questions
6.1.
What is the difference between fill_n() and fill() function?
6.2.
What is subsequence?
6.3.
What is the difference between substring and subsequence?
7.
Conclusion
Last Updated: Mar 27, 2024
Hard

Maximum sum subsequence of any size which is decreasing-increasing alternatively

Author Ayush Tiwari
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

An array, as we all know, is one of the most powerful and widely used data structures in computer languages. An array is a type of data structure that may hold comparable types of data. It is a very popular topic asked in coding interviews and one must practice questions on arrays to get a good grip on this topic. This blog will discuss the approach to solving the maximum sum subsequence of any size that is decreasing and increasing alternatively. Before jumping on the approach to the problem, let us first understand the problem.

Array Example

Problem statement

Given an array, find the maximum sum subsequence whose elements are increasing and decreasing alternatively. Here, increasing and decreasing alternatively means that all the elements follow the same manner.

To understand it more clearly, let’s take an array [6, 4, 10, 9, 25, 16], as we can see that this array is decreasing and increasing in alternating order. As 4 is less than both 10 and 6 and 10 is greater than both 4 and 9, and so on. We have to find the maximum sum subsequence of this array.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Problem example

Input 1

Input 1

Output 1

5

 

Explanation: The maximum sum subsequence that is increasing and decreasing alternatively is  [1, 0, 1, 0, 3] and the resultant sum is 5.

 

Input 2

input2

Output 2

18

 

Explanation: The maximum sum subsequence that is increasing and decreasing alternatively is [2, 5, 3, 8] and the resultant sum is 18.

 

Input 3

input 3

Output 3

26

 

Explanation: The maximum sum subsequence that is increasing and decreasing alternatively is [4, 8, 6, 8] and the resultant sum is 26.

Brute Force Approach

The brute force is simply finding all the subsequences recursively and checking the subsequence which follows the condition elements are increasing and decreasing alternatively and finding the maximum sum of it.

Algorithm

  1. Every element has two options either we take in our subsequence or just leave it. For each index, we call two recursive functions one function includes that element, and the other will not include it.
  2. The base case is if the current index is greater than the number of elements in the array then:
    1. We check if elements are increasing and decreasing alternatively.
    2. If it follows the above condition, we find the sum of the subsequence.
  3. Update the answer with a maximum sum in the base case
  4. Return the answer

Implementation

#include <bits/stdc++.h>
using namespace std;
int ans = 0;
int check(vector<int> &seq)
{
    int n = seq.size();
    // if size is 0 then return 0
    if (n == 0)
        return 0;
    // if there is one element then return the first element
    if (n == 1)
        return seq[0];
    bool cond1 = true; // when elements are a1<a2>a3<a4..
    bool cond2 = true; // when elemnts are a1>a2<a3>a4...
    int temp = 0;
    int sum = seq[0];
    for (int i = 1; i < n; i++)
    {
        // check for alternate condition where it will false
        if (temp == 0 && seq[i - 1] >= seq[i])
            cond1 = false;
        if (temp == 1 && seq[i - 1] <= seq[i])
            cond1 = false;
        if (temp == 0 && seq[i - 1] <= seq[i])
            cond2 = false;
        if (temp == 1 && seq[i - 1] >= seq[i])
            cond2 = false;
        sum = sum + seq[i];
        temp = 1 - temp;
    }
    // if any of condition is true then return sum
    // otherwise 0
    if (cond1 || cond2)
        return sum;
    else
        return 0;
}
void recursive(vector<int> &a, int n, vector<int> &seq, int curr)
{
    // base case
    if (curr >= n)
    {
        int sum = check(seq);
        ans = max(sum, ans);
        return;
    }

    // transation
    // include the current element
    seq.push_back(a[curr]);
    recursive(a, n, seq, curr + 1);
    // not include the current element
    seq.pop_back();
    recursive(a, n, seq, curr + 1);
}
// driver code
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<int> seq; // stores the subsequence
    recursive(a, n, seq, 0);
    cout << ans << endl;
}

 

Input

6
4 8 2 5 6 8

 

Output

26

Algorithm Complexity: 

Time Complexity: O(N*2^N), where N is the size of the array. It is O(2^N) because for every element we have 2 options, so, for N element 2^n options and O(N) for checking condition in each case. 

Space Complexity: O(N) as we are using a vector of at seq size; therefore, the overall space complexity will be O(N).

Efficient Approach

This approach considers using Dynamic programming along with backtracking. We need to store the maximum sum up to that particular element while traversing the array. Also, we need to store the value preceding the last element of each alternating subsequence with the maximum sum. In the iteration, we need to check the elements and the stored elements using an ‘IF’ condition as mentioned in the code. If the condition is true, add that element to the accumulated sum. Using this approach, we can find the maximum sum subsequence that is increasing and decreasing alternatively.

Algorithm 

  1. Create a function ‘getResult()’ that will accept two parameters, i.e., one array of integer ‘arr’, and the second one is the ‘N’ - the size of the vector ‘input’.
  2. Create two arrays of integers ‘maxSum’ and ‘before’ to store the maximum sum of ‘N’ elements and to store the value preceding the previous element of each alternating subsequence with the maximum sum.
  3. Make an iteration using a nested ‘for’ loop with the help of two variables ‘i’ and ‘j’, check for the ‘IF’ condition as stated in the code and if the condition is true, then update the value of variable ‘currentMax’ and if they are equal, then assign the value of the element at index ‘j’ of ‘maxSum’ to ‘currentMax’ and if not, then call the ‘helper’ function passing the parameter shown in the code and add the received value to ‘currentMax’ along with the value of the element at ‘ith’ index of ‘arr’. 
  4. In the ‘helper’ function, check for the base case, check for the conditions stated in the code, and return the value.
  5. Return the max_element value of ‘maxSum’ and ‘maxSum + N.’

Implementation

// C++ code to find the maximum sum subsequence of an array that is increasing and decreasing alternately
#include <bits/stdc++.h>
using namespace std;

// Function for backtracking
int helper(int arr[], int maxSum[], int before[], int N, int root, int bef_root, int bbef_root)
{
    // Base case:
    if (bbef_root == -1)
    {
        int index = bef_root;
        return arr[index];
    }

    // Subsequence with alternate parts
    if ((arr[root] > arr[bef_root] && arr[bbef_root] > arr[bef_root]) || (arr[root] < arr[bef_root] && arr[bbef_root] < arr[bef_root]))
    {
        return arr[bef_root] + maxSum[bbef_root];
    }

    // Case when both are equal
    else
    {
        return helper(arr, maxSum, before, N, root, bef_root, before[bbef_root]);
    }
}

// Function to get result for the maximum sum subsequence
int getResult(int arr[], int N)
{
    // Contains maximum sum according to the input vector
    int maxSum[N];
    // vector to store the index of preceeding element
    int before[N];

    fill_n(&maxSum[0], N, 0);
    maxSum[0] = arr[0];
    before[0] = -1;

    // Traverse the array
    for (int i = 1; i < N; i++)
    {
        for (int j = 0; j < i; j++)
        {
            int currentMax = 0;
            if ((arr[i] > arr[j] && arr[before[j]] > arr[j]) || (arr[i] < arr[j] && arr[before[j]] < arr[j]) || before[j] == -1)
            {
                currentMax = (arr[i] == arr[j]) ? maxSum[j] : arr[i] + maxSum[j];
            }
            else if (arr[i] == arr[j])
            {
                // if both are equal then consider it only once
                currentMax = maxSum[j];
            }

            else
            {
                // Backtracking if three elements follow the order
                currentMax = arr[i] + helper(arr, maxSum, before, N, i, j, before[before[j]]);
            }
            if (currentMax >= maxSum[i])
            {
                maxSum[i] = currentMax;
                before[i] = j;
            }
        }
    }

    // Get max result
    return *max_element(maxSum, maxSum + N);
}

// Main function for finding the maximum sum subsequence that is increasing and decreasing alternatively
int main()
{
    int n;
    cin >> n;
    int input[n];
    for (int i = 0; i < n; i++)
        cin >> input[i];

    cout << getResult(input, n) << endl;
    return 0;
}

 

Input

6
4 8 2 5 6 8

 

Output

26

Algorithm Complexity: 

Time Complexity: O(N ^ 2) where N is the size of the array. It is O(N^2) because we have to traverse the array twice.

Space Complexity: O(N) as we are using a set of at max ‘N’ size, therefore, the overall space complexity will be O(N).

Frequently Asked Questions

What is the difference between fill_n() and fill() function?

The ‘fill_n’ function is used in this code to fill some default in the ‘maxSum’ array passed in it while the 'fill' function applies the value 'val' to all items in the range [begin, end], where 'begin' is the first position and 'end' is the last.

What is subsequence?

A subsequence is the subset of a sequence. The only thing to be kept in mind is that the order can’t be changed. For example some possible subsequence of {1,2,3,4} will be {1}, {2,4}, {1,2,4}, etc. It cant be {4,3} or {2.4,3}.

What is the difference between substring and subsequence?

Both are subsets of a sequence. In substring, consecutive elements are taken, whereas in subsequence, the order is maintained, some elements are deleted. For example, {1,2,4} can’t be substring of {1,2,3,4}. It is the subsequence of {1,2,3,4}.

Conclusion

In this article, we discussed the maximum sum subsequence of any size which is decreasing-increasing alternatively, we discussed the approach to solve this problem programmatically, the time and space complexities.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Previous article
Maximum sum subsequence of any size that is decreasing-increasing alternatively
Next article
Count of valid arrays of size P with elements in the range [1, N] having duplicates at least M distance apart
Live masterclass