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

Problem example

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

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

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;
}

You can also try this code with Online C++ Compiler

Run Code

Input

6
4 8 2 5 6 8

You can also try this code with Online C++ Compiler

Run Code

Output

26

You can also try this code with Online C++ Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

Input

6
4 8 2 5 6 8

You can also try this code with Online C++ Compiler

Run Code

Output

26

You can also try this code with Online C++ Compiler

Run Code

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 Algorithms, Competitive Programming, JavaScript, System Design, Machine 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 problems, interview 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!