Given an array arr[] of size N, consisting of positive and negative integers, the task is to find the longest alternating subsequence(i.e. the sign of every element is opposite to that of its previous element) from the given array which has the maximum sum.
Examples:
Input: arr[] = {-2, 10, 3, -8, -4, -1, 5, -2, -3, 1}
Output: 11
Explanation:
Since the subsequence needs to be longest possible as well as alternating, one element can be selected from each of the following subarrays:
{-2}, {10, 3}, {-8, -4, -1}, {5}, {-2, -3}, {1}
Hence, selecting the maximum from each of the subarrays as the elements of the subsequence generates an alternating subsequence with maximum sum.
Therefore, the subsequence is {-2, 10, -1, 5, -2, 1}
Hence, the sum of the subsequence is 11.
Input: arr[] = {12, 4, -5, 7, -9}
Output: 5
Explanation:
The longest subsequence with greatest sum is {12, -5, 7, -9}.
Hence, the maximum sum is 5.
Linear Approach using extra-space:
Refer to Longest alternating subsequence which has maximum sum of elements for the linear approach using extra space.
Time Complexity: O(N)
Auxiliary Space: O(N)
Space-Efficient Approach:
To solve the problem, we can observe the following:
- To maximize the length of the alternating subsequence, we need to consider an element from every sequence of consecutive numbers of the
Illustration:
Let us consider an array arr[] = {1, 1, 2, -1, -5, 2, 1, -3}
The consecutive sequences of elements of same sign are:
{1, 1, 2}, {-1, -5}, {2, 1}, {-3}
Hence, by selecting an element from each of these sequences, an alternating subsequence of the longest possible length can be obtained.
- To maximize the sum of the subsequence, we need to select the maximum from each consecutive subsequence of elements of the same sign.
Illustration:
For the array arr[] = {1, 1, 2, -1, -5, 2, 1, -3}, the consecutive sequences of elements of sign were observed to be:
{1, 1, 2}, {-1, -5}, {2, 1}, {-3}
Therefore, the subsequence with the maximum sum is {2, -1, 2, -3}, formed by selecting the maximum element from each of the sequences.
Follow the steps below to solve the problem efficiently:
- Iterate over the array using Two Pointers.
- Set i = 0, and set j = i.
- Traverse the array until j points to an index consisting of an element of sign opposite to that of arr[i]. At every traversal, update the maximum element encountered between [i, j].
- Once an element of opposite sign is found, add the maximum from the sequence [i, j) to maxsum.
- Set i = j, and repeat the above two steps until the entire array is traversed.
- Print the final value of maxsum as the answer.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to check the// sign of the elementint sign(int x){ if (x > 0) return 1; else return -1;}// Function to calculate and// return the maximum sum of// longest alternating subsequenceint findMaxSum(int arr[], int size){ int max_sum = 0, pres, i, j; // Iterate through the array for (i = 0; i < size; i++) { // Stores the first element of // a sequence of same sign pres = arr[i]; j = i; // Traverse until an element with // opposite sign is encountered while (j < size && sign(arr[i]) == sign(arr[j])) { // Update the maximum pres = max(pres, arr[j]); j++; } // Update the maximum sum max_sum = max_sum + pres; // Update i i = j - 1; } // Return the maximum sum return max_sum;}// Driver Codeint main(){ int arr[] = { -2, 8, 3, 8, -4, -15, 5, -2, -3, 1 }; int size = sizeof(arr) / sizeof(arr[0]); cout << findMaxSum(arr, size); return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{ // Function to check the // sign of the element static int sign(int x) { if (x > 0) return 1; else return -1; } // Function to calculate and // return the maximum sum of // longest alternating subsequence static int findMaxSum(int arr[], int size) { int max_sum = 0, pres, i, j; // Iterate through the array for (i = 0; i < size; i++) { // Stores the first element of // a sequence of same sign pres = arr[i]; j = i; // Traverse until an element with // opposite sign is encountered while (j < size && sign(arr[i]) == sign(arr[j])) { // Update the maximum pres = Math.max(pres, arr[j]); j++; } // Update the maximum sum max_sum = max_sum + pres; // Update i i = j - 1; } // Return the maximum sum return max_sum; } // Driver Code public static void main(String[] args) { int arr[] = { -2, 8, 3, 8, -4, -15, 5, -2, -3, 1 }; int size = arr.length; System.out.println(findMaxSum(arr, size)); }}// This code is contributed by sapnasingh4991 |
Python
# Python3 program to implement# the above approach# Function to check the# sign of the elementdef sign(x): if (x > 0): return 1 else: return -1# Function to calculate and# return the maximum sum of# longest alternating subsequencedef findMaxSum(arr, size): max_sum = 0 # Iterate through the array i = 0 while i < size: # Stores the first element of # a sequence of same sign pres = arr[i] j = i # Traverse until an element with # opposite sign is encountered while (j < size and (sign(arr[i]) == sign(arr[j]))): # Update the maximum pres = max(pres, arr[j]) j += 1 # Update the maximum sum max_sum = max_sum + pres # Update i i = j - 1 i += 1 # Return the maximum sum return max_sum# Driver Codeif __name__ == "__main__": arr = [ -2, 8, 3, 8, -4, -15, 5, -2, -3, 1 ] size = len(arr) print(findMaxSum(arr, size))# This code is contributed by chitranayal |
C#
// C# Program to implement// the above approachusing System;class GFG{ // Function to check the // sign of the element static int sign(int x) { if (x > 0) return 1; else return -1; } // Function to calculate and // return the maximum sum of // longest alternating subsequence static int findMaxSum(int []arr, int size) { int max_sum = 0, pres, i, j; // Iterate through the array for (i = 0; i < size; i++) { // Stores the first element of // a sequence of same sign pres = arr[i]; j = i; // Traverse until an element with // opposite sign is encountered while (j < size && sign(arr[i]) == sign(arr[j])) { // Update the maximum pres = Math.Max(pres, arr[j]); j++; } // Update the maximum sum max_sum = max_sum + pres; // Update i i = j - 1; } // Return the maximum sum return max_sum; } // Driver Code public static void Main(String[] args) { int []arr = { -2, 8, 3, 8, -4, -15, 5, -2, -3, 1 }; int size = arr.Length; Console.WriteLine(findMaxSum(arr, size)); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// javascript program to implement// the above approach // Function to check the // sign of the element function sign(x) { if (x > 0) return 1; else return -1; } // Function to calculate and // return the maximum sum of // longest alternating subsequence function findMaxSum(arr, size) { let max_sum = 0, pres, i, j; // Iterate through the array for (i = 0; i < size; i++) { // Stores the first element of // a sequence of same sign pres = arr[i]; j = i; // Traverse until an element with // opposite sign is encountered while (j < size && sign(arr[i]) == sign(arr[j])) { // Update the maximum pres = Math.max(pres, arr[j]); j++; } // Update the maximum sum max_sum = max_sum + pres; // Update i i = j - 1; } // Return the maximum sum return max_sum; } // Driver Code let arr = [ -2, 8, 3, 8, -4, -15, 5, -2, -3, 1 ]; let size = arr.length; document.write(findMaxSum(arr, size)); // This code is contributed by avijitmondal1998.</script> |
6
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!
