Maximum subsequence sum such that no three are consecutive in O(1) space

0 0 6 minutes read

Given an array A[] of N positive numbers, the task is to find the maximum sum that can be formed which has no three consecutive elements present.

Examples:

Input: A[] = {1, 2, 3}, N=3
Output: 5
Explanation: Three of them can’t be taken together so answer is 2 + 3 = 5

Input: A[] = {3000, 2000, 1000, 3, 10}, N=5
Output: 5013

A O(N) approach that takes O(N) auxiliary space has been discussed here. This can be further optimized with the following approach that takes O(1) extra space.

O(1) Space Approach: From the above approach, we can conclude that for calculating sum[i], only the values of sum[i-1], sum[i-2] and sum[i-3] are relevant.This observation can help to discard the sum array completely and instead just maintain some variables to solve the problem using O(1) auxiliary space.

Follow the steps below to solve the problem:

Initialize the following variables to be used:
- sum: This stores the final sum such that no three elements are consecutive.
- first: This stores the subsequence sum up to index i-1.
- second: This stores the subsequence sum up to index i-2.
- third: This stores the subsequence sum up to index i-3.
If N<3, the answer would be the sum of all the elements as there will be no consecutives.
Otherwise, do the following:
- Initialize third with A[0]
- Initialize second with A[0]+A[1]
- Initialize first with max(second, A[1]+A[2])
- Initialize sum with the maximum among first, second, and third.
- Iterate from 3 to N-1, and do the following for each current index i:
  - There can be the following three cases:
    - Exclude A[i], i.e. sum = first
    - Exclude A[i-1], i.e., sum = second + A[i]
    - Exclude A[i-2], i.e., sum = third + A[i] + A[i-1]
  - Thus, sum is updated as the maximum between first, (second+A[i]) and (third+A[i]+A[i-1])
  - Update third with second, second with first and first with sum.
Finally, return sum.

Below is the implementation of the above approach:

C++

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the  maximum subsequence sum such
// that no three elements are consecutive
int maxSumWO3Consec(int A[], int N)
{
    // when N is 1, answer would be the only element present
    if (N == 1)
        return A[0];
    // when N is 2, answer would be sum of elements
    if (N == 2)
        return A[0] + A[1];
    // variable to store sum up to i - 3
    int third = A[0];
 
    // variable to store sum up to i - 2
    int second = third + A[1];
 
    // variable to store sum up to i - 1
    int first = max(second, A[1] + A[2]);
 
    // variable to store the final sum of the subsequence
    int sum = max(max(third, second), first);
 
    for (int i = 3; i < N; i++) {
        // find the maximum subsequence sum up to index i
        sum = max(max(first, second + A[i]),
                  third + A[i] + A[i - 1]);
 
        // update first, second and third
        third = second;
        second = first;
        first = sum;
    }
    // return ans;
    return sum;
}
 
// Driver code
int main()
{
    // Input
    int A[] = { 3000, 2000, 1000, 3, 10 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function call
    cout << maxSumWO3Consec(A, N);
   
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG 
{
   
    // Function to calculate the  maximum subsequence sum
    // such
    // that no three elements are consecutive
    public static int maxSumWO3Consec(int A[], int N)
    {
       
        // when N is 1, answer would be the only element
        // present
        if (N == 1)
            return A[0];
        // when N is 2, answer would be sum of elements
        if (N == 2)
            return A[0] + A[1];
        // variable to store sum up to i - 3
        int third = A[0];
 
        // variable to store sum up to i - 2
        int second = third + A[1];
 
        // variable to store sum up to i - 1
        int first = Math.max(second, A[1] + A[2]);
 
        // variable to store the final sum of the
        // subsequence
        int sum = Math.max(Math.max(third, second), first);
 
        for (int i = 3; i < N; i++)
        {
           
            // find the maximum subsequence sum up to index
            // i
            sum = Math.max(Math.max(first, second + A[i]),
                           third + A[i] + A[i - 1]);
 
            // update first, second and third
            third = second;
            second = first;
            first = sum;
        }
        // return ans;
        return sum;
    }
 
    public static void main(String[] args)
    {
        // Input
        int A[] = { 3000, 2000, 1000, 3, 10 };
        int N = A.length;
 
        // Function call
        int res = maxSumWO3Consec(A, N);
        System.out.println(res);
       
    }
}
 
//This code is contributed by Potta Lokesh

Python3

# Python 3 implementation for the above approach
 
# Function to calculate the  maximum subsequence sum such
# that no three elements are consecutive
def maxSumWO3Consec(A, N):
   
    # when N is 1, answer would be the only element present
    if (N == 1):
        return A[0]
       
    # when N is 2, answer would be sum of elements
    if (N == 2):
        return A[0] + A[1]
       
    # variable to store sum up to i - 3
    third = A[0]
 
    # variable to store sum up to i - 2
    second = third + A[1]
 
    # variable to store sum up to i - 1
    first = max(second, A[1] + A[2])
 
    # variable to store the final sum of the subsequence
    sum = max(max(third, second), first)
 
    for i in range(3,N,1):
       
        # find the maximum subsequence sum up to index i
        sum = max(max(first, second + A[i]), third + A[i] + A[i - 1])
 
        # update first, second and third
        third = second
        second = first
        first = sum
    # return ans;
    return sum
 
# Driver code
if __name__ == '__main__':
   
    # Input
    A = [3000, 2000, 1000, 3, 10]
    N = len(A)
 
    # Function call
    print(maxSumWO3Consec(A, N))
     
    # This code is contributed by ipg2016107.

C#

// C# program for the above approach
using System;
 
class GFG {
 
    // Function to calculate the  maximum subsequence sum
    // such
    // that no three elements are consecutive
    public static int maxSumWO3Consec(int[] A, int N)
    {
 
        // when N is 1, answer would be the only element
        // present
        if (N == 1)
            return A[0];
        // when N is 2, answer would be sum of elements
        if (N == 2)
            return A[0] + A[1];
        // variable to store sum up to i - 3
        int third = A[0];
 
        // variable to store sum up to i - 2
        int second = third + A[1];
 
        // variable to store sum up to i - 1
        int first = Math.Max(second, A[1] + A[2]);
 
        // variable to store the final sum of the
        // subsequence
        int sum = Math.Max(Math.Max(third, second), first);
 
        for (int i = 3; i < N; i++) {
 
            // find the maximum subsequence sum up to index
            // i
            sum = Math.Max(Math.Max(first, second + A[i]),
                           third + A[i] + A[i - 1]);
 
            // update first, second and third
            third = second;
            second = first;
            first = sum;
        }
        // return ans;
        return sum;
    }
 
    // Driver Code
    public static void Main()
    {
        // Input
        int[] A = { 3000, 2000, 1000, 3, 10 };
        int N = A.Length;
 
        // Function call
        int res = maxSumWO3Consec(A, N);
        Console.Write(res);
    }
}

Javascript

<script>
        // JavaScript implementation for the above approach
 
        // Function to calculate the  maximum subsequence sum such
        // that no three elements are consecutive
        function maxSumWO3Consec(A, N)
        {
         
            // when N is 1, answer would be the only element present
            if (N == 1)
                return A[0];
            // when N is 2, answer would be sum of elements
            if (N == 2)
                return A[0] + A[1];
            // variable to store sum up to i - 3
            let third = A[0];
 
            // variable to store sum up to i - 2
            let second = third + A[1];
 
            // variable to store sum up to i - 1
            let first = Math.max(second, A[1] + A[2]);
 
            // variable to store the final sum of the subsequence
            let sum = Math.max(Math.max(third, second), first);
 
            for (let i = 3; i < N; i++) {
                // find the maximum subsequence sum up to index i
                sum = Math.max(Math.max(first, second + A[i]),
                    third + A[i] + A[i - 1]);
 
                // update first, second and third
                third = second;
                second = first;
                first = sum;
            }
            // return ans;
            return sum;
        }
 
        // Driver code
 
        // Input
        let A = [3000, 2000, 1000, 3, 10];
        let N = A.length;
 
        // Function call
        document.write(maxSumWO3Consec(A, N));
 
//This code is contributed by Potta Lokesh
    </script>

Output:

Time complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!