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 = 5Input: 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.
- There can be the following three cases:
- 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> |
5013
Time complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!