Maximum Sum Subsequence

Given an array arr[] of size N, the task is to find the maximum sum non-empty subsequence present in the given array.

Examples:

Input: arr[] = { 2, 3, 7, 1, 9 } 
Output: 22 
Explanation: 
Sum of the subsequence { arr[0], arr[1], arr[2], arr[3], arr[4] } is equal to 22, which is the maximum possible sum of any subsequence of the array. 
Therefore, the required output is 22.

Input: arr[] = { -2, 11, -4, 2, -3, -10 } 
Output: 13 
Explanation: 
Sum of the subsequence { arr[1], arr[3] } is equal to 13, which is the maximum possible sum of any subsequence of the array. 
Therefore, the required output is 13.

Naive Approach: The simplest approach to solve this problem is to generate all possible non-empty subsequences of the array and calculate the sum of each subsequence of the array. Finally, print the maximum sum obtained from the subsequence.

 Time Complexity: O(N * 2^N) 
Auxiliary Space: O(N)

Efficient Approach: The idea is to traverse the array and calculate the sum of positive elements of the array and print the sum obtained. Follow the steps below to solve the problem:

• Check if the largest element of the array is greater than 0 or not. If found to be true, then traverse the array and print the sum of all positive elements of the array.
• Otherwise, print the largest element present in the array.

Below is the implementation of the above approach:

// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to print the maximum // non-empty subsequence sum int MaxNonEmpSubSeq(int a[], int n) {  // Stores the maximum non-empty  // subsequence sum in an array  int sum = 0;  // Stores the largest element  // in the array  int max = *max_element(a, a + n);  if (max <= 0) {  return max;  }  // Traverse the array  for (int i = 0; i < n; i++) {  // If a[i] is greater than 0  if (a[i] > 0) {  // Update sum  sum += a[i];  }  }  return sum; } // Driver Code int main() {  int arr[] = { -2, 11, -4, 2, -3, -10 };  int N = sizeof(arr) / sizeof(arr[0]);  cout << MaxNonEmpSubSeq(arr, N);  return 0; } 

// Java program to implement // the above approach import java.util.*; class GFG {  // Function to print the maximum  // non-empty subsequence sum  static int MaxNonEmpSubSeq(int a[], int n)  {  // Stores the maximum non-empty  // subsequence sum in an array  int sum = 0;  // Stores the largest element  // in the array  int max = a[0];  for(int i = 1; i < n; i++)  {  if(max < a[i])  {  max = a[i];  }  }  if (max <= 0)   {   return max;  }  // Traverse the array  for (int i = 0; i < n; i++)  {  // If a[i] is greater than 0  if (a[i] > 0)   {  // Update sum  sum += a[i];  }  }  return sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { -2, 11, -4, 2, -3, -10 };  int N = arr.length;  System.out.println(MaxNonEmpSubSeq(arr, N));  } } // This code is contributed by divyesh072019 

# Python3 program to implement # the above approach # Function to print the maximum # non-empty subsequence sum def MaxNonEmpSubSeq(a, n): # Stores the maximum non-empty # subsequence sum in an array sum = 0 # Stores the largest element # in the array maxm = max(a) if (maxm <= 0): return maxm # Traverse the array for i in range(n): # If a[i] is greater than 0 if (a[i] > 0): # Update sum sum += a[i] return sum # Driver Code if __name__ == '__main__': arr = [ -2, 11, -4, 2, -3, -10 ] N = len(arr) print(MaxNonEmpSubSeq(arr, N)) # This code is contributed by mohit kumar 29 

// C# program to implement // the above approach using System; class GFG{   // Function to print the maximum // non-empty subsequence sum static int MaxNonEmpSubSeq(int[] a, int n) {    // Stores the maximum non-empty  // subsequence sum in an array  int sum = 0;    // Stores the largest element  // in the array  int max = a[0];  for(int i = 1; i < n; i++)  {  if (max < a[i])  {  max = a[i];  }  }    if (max <= 0)   {  return max;  }    // Traverse the array  for(int i = 0; i < n; i++)   {    // If a[i] is greater than 0  if (a[i] > 0)  {    // Update sum  sum += a[i];  }  }  return sum; } // Driver Code static void Main()  {  int[] arr = { -2, 11, -4, 2, -3, -10 };  int N = arr.Length;    Console.WriteLine(MaxNonEmpSubSeq(arr, N)); } } // This code is contributed by divyeshrabadiya07 

<script>  // Javascript program to implement  // the above approach    // Function to print the maximum  // non-empty subsequence sum  function MaxNonEmpSubSeq(a, n)  {  // Stores the maximum non-empty  // subsequence sum in an array  let sum = 0;  // Stores the largest element  // in the array  let max = a[0];  for(let i = 1; i < n; i++)  {  if (max < a[i])  {  max = a[i];  }  }  if (max <= 0)  {  return max;  }  // Traverse the array  for(let i = 0; i < n; i++)  {  // If a[i] is greater than 0  if (a[i] > 0)  {  // Update sum  sum += a[i];  }  }  return sum;  }    let arr = [ -2, 11, -4, 2, -3, -10 ];  let N = arr.length;    document.write(MaxNonEmpSubSeq(arr, N));   </script> 

13

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