# Find the length of largest subsequence with positive sum

In this article, we will discuss a C program to find the length of the largest subsequence with a positive sum. We will provide a detailed explanation of the problem statement, present the pseudocode algorithm with step-by-step explanations, and analyze the time complexity of the code. Additionally, we will provide the resultant output explanation for better understanding.

## Problem Statement

Given an array of integers, the task is to find the length of the largest subsequence with a positive sum. A subsequence is defined as a sequence of elements taken from the array, but not necessarily contiguous.

## Pseudocode Algorithm

```1. Define a function named printData that takes an array and its size as parameters.
2. Iterate through the array and print each element.
3. Define a recursive function named longestPositiveSequence that takes the array, its size, current index (i), current sum (sum), current length (n), and maximum length (pos) as parameters.
4. If the current index (i) is equal to the size of the array, check if the current sum (sum) is positive and the current length (n) is greater than 0.
a. If both conditions are satisfied, return the current length (n).
b. Otherwise, return the maximum length (pos).
5. Call the longestPositiveSequence function recursively twice:
a. First, by incrementing the current index (i) and passing the current sum (sum) and current length (n).
b. Second, by incrementing the current index (i), adding the current element to the sum, incrementing the current length (n), and passing the maximum length (pos).
6. Return the maximum length (pos) obtained from the above two recursive calls.
7. In the main function:
a. Define two arrays with different integer values.
b. Get the size of the arrays using the sizeof operator.
c. Call the printData function to print the array elements.
d. Call the longestPositiveSequence function for each array and print the length of the longest positive subsequence.```

## Code Solution

``````/*
C Program
Find the length of largest subsequence with positive sum
*/
#include <stdio.h>

void printData(int arr[],int size)
{
printf("\n Array elements \n");
for (int i = 0; i < size; ++i)
{
printf(" %d",arr[i]);
}
printf("\n");
}

// Find the length of longest positive sum subsequence
int longestPositiveSequence(int arr[], int size, int i, int sum,int n,  int pos)
{
if(pos == size)
{
// When sum of all elements are not negative
return pos;
}

if (i == size)
{
if(n > 0 && sum >= 0 && pos < n)
{
// Found new longest positive subsequence
return n;
}
return pos;
}

int p = longestPositiveSequence(arr, size, i + 1, sum,n,pos);

return longestPositiveSequence(arr, size, i + 1, sum + arr[i],n+1,p);

}

int main(int argc, char const *argv[])
{
int arr1[] =
{
-4, 5, 1, -2, -7, 3, -4
};
int arr2[] =
{
-6, 2, 2 ,-1
};
// Get the number of element in array
int size = sizeof(arr1) / sizeof(arr1);

printData(arr1, size);

int length = longestPositiveSequence(arr1, size, 0, 0, 0, 0);
printf(" Length of Longest Positive SubSequence is : %d \n",length);

// Case 2
size = sizeof(arr2) / sizeof(arr2);

printData(arr2, size);

length =  longestPositiveSequence(arr2, size, 0, 0,0,0);

printf(" Length of Longest Positive SubSequence is : %d \n",length);

return 0;
}
``````

#### Output

`````` Array elements
-4 5 1 -2 -7 3 -4
Length of Longest Positive SubSequence is : 5

Array elements
-6 2 2 -1
Length of Longest Positive SubSequence is : 3``````
``````/*
Java program
Find the length of largest subsequence with positive sum
*/
public class Subsequence
{
public void printData(int[] arr, int size)
{
System.out.print("\n Array elements \n");
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
// Find the length of longest positive sum subsequence
public int longestPositiveSequence(int[] arr, int size, int i, int sum, int n, int pos)
{
if (pos == size)
{
// When sum of all elements are not negative
return pos;
}
if (i == size)
{
if (n > 0 && sum >= 0 && pos < n)
{
// Found new longest positive subsequence
return n;
}
return pos;
}
int p = longestPositiveSequence(arr, size, i + 1, sum, n, pos);
return longestPositiveSequence(arr, size, i + 1, sum + arr[i], n + 1, p);
}
public static void main(String[] args)
{
int[] arr1 = {
-4 , 5 , 1 , -2 , -7 , 3 , -4
};
int[] arr2 = {
-6 , 2 , 2 , -1
};
// Get the number of element in array
int size = arr1.length;
int length = task.longestPositiveSequence(arr1, size, 0, 0, 0 ,0);
// [-4 , 5 , 1 , -2 , 3 ] or [- 5 , 1 , -2 , 3 , -4]
System.out.print(" Length of Longest Positive SubSequence is : " + length);
// Case 2
size = arr2.length;;
length = task.longestPositiveSequence(arr2, size, 0, 0, 0 , 0);
System.out.print(" Length of Longest Positive SubSequence is : " + length);
}
}``````

#### Output

`````` Array elements
-4 5 1 -2 -7 3 -4
Length of Longest Positive SubSequence is : 5
Array elements
-6 2 2 -1
Length of Longest Positive SubSequence is : 3``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ program
Find the length of largest subsequence with positive sum
*/

class Subsequence
{
public: void printData(int arr[], int size)
{
cout << "\n Array elements \n";
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
// Find the length of longest positive sum subsequence
int longestPositiveSequence(int arr[], int size, int i, int sum, int n, int pos)
{
if (pos == size)
{
// When sum of all elements are not negative
return pos;
}
if (i == size)
{
if (n > 0 && sum >= 0 && pos < n)
{
// Found new longest positive subsequence
return n;
}
return pos;
}
int p = this->longestPositiveSequence(arr, size, i + 1, sum, n, pos);
return this->longestPositiveSequence(arr, size, i + 1, sum + arr[i], n + 1, p);
}
};
int main()
{
int arr1[] = {
-4 , 5 , 1 , -2 , -7 , 3 , -4
};
int arr2[] = {
-6 , 2 , 2 , -1
};
// Get the number of element in array
int size = sizeof(arr1) / sizeof(arr1);
int length = task.longestPositiveSequence(arr1, size, 0, 0, 0, 0);
// [-4 , 5 , 1 , -2 , 3 ] or [- 5 , 1 , -2 , 3 , -4]
cout << " Length of Longest Positive SubSequence is : " << length;
// Case 2
size = sizeof(arr2) / sizeof(arr2);;
length = task.longestPositiveSequence(arr2, size, 0, 0, 0, 0);
cout << " Length of Longest Positive SubSequence is : " << length;
return 0;
}``````

#### Output

`````` Array elements
-4 5 1 -2 -7 3 -4
Length of Longest Positive SubSequence is : 5
Array elements
-6 2 2 -1
Length of Longest Positive SubSequence is : 3``````
``````// Include namespace system
using System;
/*
C# program
Find the length of largest subsequence with positive sum
*/
public class Subsequence
{
public void printData(int[] arr, int size)
{
Console.Write("\n Array elements \n");
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
// Find the length of longest positive sum subsequence
public int longestPositiveSequence(int[] arr, int size, int i, int sum, int n, int pos)
{
if (pos == size)
{
// When sum of all elements are not negative
return pos;
}
if (i == size)
{
if (n > 0 && sum >= 0 && pos < n)
{
// Found new longest positive subsequence
return n;
}
return pos;
}
int p = longestPositiveSequence(arr, size, i + 1, sum, n, pos);
return longestPositiveSequence(arr, size, i + 1, sum + arr[i], n + 1, p);
}
public static void Main(String[] args)
{
int[] arr1 = {
-4 , 5 , 1 , -2 , -7 , 3 , -4
};
int[] arr2 = {
-6 , 2 , 2 , -1
};
// Get the number of element in array
int size = arr1.Length;
int length = task.longestPositiveSequence(arr1, size, 0, 0, 0, 0);
// [-4 , 5 , 1 , -2 , 3 ] or [- 5 , 1 , -2 , 3 , -4]
Console.Write(" Length of Longest Positive SubSequence is : " + length);
// Case 2
size = arr2.Length;;
length = task.longestPositiveSequence(arr2, size, 0, 0, 0, 0);
Console.Write(" Length of Longest Positive SubSequence is : " + length);
}
}``````

#### Output

`````` Array elements
-4 5 1 -2 -7 3 -4
Length of Longest Positive SubSequence is : 5
Array elements
-6 2 2 -1
Length of Longest Positive SubSequence is : 3``````
``````<?php
/*
Php program
Find the length of largest subsequence with positive sum
*/
class Subsequence
{
public	function printData( & \$arr, \$size)
{
echo "\n Array elements \n";
for (\$i = 0; \$i < \$size; ++\$i)
{
echo " ". \$arr[\$i];
}
echo "\n";
}
// Find the length of longest positive sum subsequence
public	function longestPositiveSequence( & \$arr, \$size, \$i, \$sum, \$n, \$pos)
{
if (\$pos == \$size)
{
// When sum of all elements are not negative
return \$pos;
}
if (\$i == \$size)
{
if (\$n > 0 && \$sum >= 0 && \$pos < \$n)
{
// Found new longest positive subsequence
return \$n;
}
return \$pos;
}
\$p = \$this->longestPositiveSequence(\$arr, \$size, \$i + 1, \$sum, \$n, \$pos);
return \$this->longestPositiveSequence(\$arr, \$size, \$i + 1, \$sum + \$arr[\$i], \$n + 1, \$p);
}
}

function main()
{
\$arr1 = array(-4, 5, 1, -2, -7, 3, -4);
\$arr2 = array(-6, 2, 2, -1);
// Get the number of element in array
\$size = count(\$arr1);
\$length = \$task->longestPositiveSequence(\$arr1, \$size, 0, 0, 0, 0);
// [-4 , 5 , 1 , -2 , 3 ] or [- 5 , 1 , -2 , 3 , -4]
echo " Length of Longest Positive SubSequence is : ". \$length;
// Case 2
\$size = count(\$arr2);;
\$length = \$task->longestPositiveSequence(\$arr2, \$size, 0, 0, 0, 0);
echo " Length of Longest Positive SubSequence is : ". \$length;
}
main();``````

#### Output

`````` Array elements
-4 5 1 -2 -7 3 -4
Length of Longest Positive SubSequence is : 5
Array elements
-6 2 2 -1
Length of Longest Positive SubSequence is : 3``````
``````/*
Node Js program
Find the length of largest subsequence with positive sum
*/
class Subsequence
{
printData(arr, size)
{
process.stdout.write("\n Array elements \n");
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
// Find the length of longest positive sum subsequence
longestPositiveSequence(arr, size, i, sum, n, pos)
{
if (pos == size)
{
// When sum of all elements are not negative
return pos;
}
if (i == size)
{
if (n > 0 && sum >= 0 && pos < n)
{
// Found new longest positive subsequence
return n;
}
return pos;
}
var p = this.longestPositiveSequence(arr, size, i + 1, sum, n, pos);
return this.longestPositiveSequence(arr, size, i + 1, sum + arr[i], n + 1, p);
}
}

function main()
{
var arr1 = [-4, 5, 1, -2, -7, 3, -4];
var arr2 = [-6, 2, 2, -1];
// Get the number of element in array
var size = arr1.length;
var length = task.longestPositiveSequence(arr1, size, 0, 0, 0, 0);
// [-4 , 5 , 1 , -2 , 3 ] or [- 5 , 1 , -2 , 3 , -4]
process.stdout.write(" Length of Longest Positive SubSequence is : " + length);
// Case 2
size = arr2.length;;
length = task.longestPositiveSequence(arr2, size, 0, 0, 0, 0);
process.stdout.write(" Length of Longest Positive SubSequence is : " + length);
}
main();``````

#### Output

`````` Array elements
-4 5 1 -2 -7 3 -4
Length of Longest Positive SubSequence is : 5
Array elements
-6 2 2 -1
Length of Longest Positive SubSequence is : 3``````
``````#   Python 3 program
#   Find the length of largest subsequence with positive sum

class Subsequence :
def printData(self, arr, size) :
print("\n Array elements ")
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1

print(end = "\n")

#  Find the length of longest positive sum subsequence
def longestPositiveSequence(self, arr, size, i, sum, n, pos) :
if (pos == size) :
#  When sum of all elements are not negative
return pos

if (i == size) :
if (n > 0 and sum >= 0 and pos < n) :
#  Found new longest positive subsequence
return n

return pos

p = self.longestPositiveSequence(arr, size, i + 1, sum, n, pos)
return self.longestPositiveSequence(arr, size, i + 1, sum + arr[i], n + 1, p)

def main() :
arr1 = [-4, 5, 1, -2, -7, 3, -4]
arr2 = [-6, 2, 2, -1]
#  Get the number of element in array
size = len(arr1)
length = task.longestPositiveSequence(arr1, size, 0, 0, 0, 0)
#  [-4 , 5 , 1 , -2 , 3 ] or [- 5 , 1 , -2 , 3 , -4]
print(" Length of Longest Positive SubSequence is : ", length, end = "")
#  Case 2
size = len(arr2)
length = task.longestPositiveSequence(arr2, size, 0, 0, 0, 0)
print(" Length of Longest Positive SubSequence is : ", length, end = "")

if __name__ == "__main__": main()``````

#### Output

`````` Array elements
-4  5  1  -2  -7  3  -4
Length of Longest Positive SubSequence is :  5
Array elements
-6  2  2  -1
Length of Longest Positive SubSequence is :  3``````
``````#   Ruby program
#   Find the length of largest subsequence with positive sum

class Subsequence
def printData(arr, size)
print("\n Array elements \n")
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end

print("\n")
end

#  Find the length of longest positive sum subsequence
def longestPositiveSequence(arr, size, i, sum, n, pos)
if (pos == size)
#  When sum of all elements are not negative
return pos
end

if (i == size)
if (n > 0 && sum >= 0 && pos < n)
#  Found new longest positive subsequence
return n
end

return pos
end

p = self.longestPositiveSequence(arr, size, i + 1, sum, n, pos)
return self.longestPositiveSequence(arr, size, i + 1, sum + arr[i], n + 1, p)
end

end

def main()
arr1 = [-4, 5, 1, -2, -7, 3, -4]
arr2 = [-6, 2, 2, -1]
#  Get the number of element in array
size = arr1.length
length = task.longestPositiveSequence(arr1, size, 0, 0, 0, 0)
#  [-4 , 5 , 1 , -2 , 3 ] or [- 5 , 1 , -2 , 3 , -4]
print(" Length of Longest Positive SubSequence is : ", length)
#  Case 2
size = arr2.length
length = task.longestPositiveSequence(arr2, size, 0, 0, 0, 0)
print(" Length of Longest Positive SubSequence is : ", length)
end

main()``````

#### Output

`````` Array elements
-4 5 1 -2 -7 3 -4
Length of Longest Positive SubSequence is : 5
Array elements
-6 2 2 -1
Length of Longest Positive SubSequence is : 3``````
``````/*
Scala program
Find the length of largest subsequence with positive sum
*/
class Subsequence
{
def printData(arr: Array[Int], size: Int): Unit = {
print("\n Array elements \n");
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
// Find the length of longest positive sum subsequence
def longestPositiveSequence(arr: Array[Int], size: Int, i: Int, sum: Int, n: Int, pos: Int): Int = {
if (pos == size)
{
// When sum of all elements are not negative
return pos;
}
if (i == size)
{
if (n > 0 && sum >= 0 && pos < n)
{
// Found new longest positive subsequence
return n;
}
return pos;
}
var p: Int = this.longestPositiveSequence(arr, size, i + 1, sum, n, pos);
return this.longestPositiveSequence(arr, size, i + 1, sum + arr(i), n + 1, p);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subsequence = new Subsequence();
var arr1: Array[Int] = Array(-4, 5, 1, -2, -7, 3, -4);
var arr2: Array[Int] = Array(-6, 2, 2, -1);
// Get the number of element in array
var size: Int = arr1.length;
var length: Int = task.longestPositiveSequence(arr1, size, 0, 0, 0, 0);
// [-4 , 5 , 1 , -2 , 3 ] or [- 5 , 1 , -2 , 3 , -4]
print(" Length of Longest Positive SubSequence is : " + length);
// Case 2
size = arr2.length;;
length = task.longestPositiveSequence(arr2, size, 0, 0, 0, 0);
print(" Length of Longest Positive SubSequence is : " + length);
}
}``````

#### Output

`````` Array elements
-4 5 1 -2 -7 3 -4
Length of Longest Positive SubSequence is : 5
Array elements
-6 2 2 -1
Length of Longest Positive SubSequence is : 3``````
``````/*
Swift 4 program
Find the length of largest subsequence with positive sum
*/
class Subsequence
{
func printData(_ arr: [Int], _ size: Int)
{
print("\n Array elements ");
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
// Find the length of longest positive sum subsequence
func longestPositiveSequence(_ arr: [Int], _ size: Int, _ i: Int, _ sum: Int, _ n: Int, _ pos: Int)->Int
{
if (pos == size)
{
// When sum of all elements are not negative
return pos;
}
if (i == size)
{
if (n > 0 && sum >= 0 && pos < n)
{
// Found new longest positive subsequence
return n;
}
return pos;
}
let p: Int = self.longestPositiveSequence(arr, size, i + 1, sum, n, pos);
return self.longestPositiveSequence(arr, size, i + 1, sum + arr[i], n + 1, p);
}
}
func main()
{
let arr1: [Int] = [-4, 5, 1, -2, -7, 3, -4];
let arr2: [Int] = [-6, 2, 2, -1];
// Get the number of element in array
var size: Int = arr1.count;
var length: Int = task.longestPositiveSequence(arr1, size, 0, 0, 0, 0);
// [-4 , 5 , 1 , -2 , 3 ] or [- 5 , 1 , -2 , 3 , -4]
print(" Length of Longest Positive SubSequence is : ", length, terminator: "");
// Case 2
size = arr2.count;
length = task.longestPositiveSequence(arr2, size, 0, 0, 0, 0);
print(" Length of Longest Positive SubSequence is : ", length, terminator: "");
}
main();``````

#### Output

`````` Array elements
-4  5  1  -2  -7  3  -4
Length of Longest Positive SubSequence is :  5
Array elements
-6  2  2  -1
Length of Longest Positive SubSequence is :  3``````

## Resultant Output Explanation:

The code provides two example cases to demonstrate the functionality of the longestPositiveSequence function.

Case 1:

```Array elements: -4 5 1 -2 -7 3 -4
Explanation: The longest subsequence with a positive sum in this array is [5, 1, 3], with a length of 3.
Output: Length of Longest Positive Subsequence is 3
```

Case 2:

```Array elements: -6 2 2 -1
Explanation: The longest subsequence with a positive sum in this array is [2, 2], with a length of 2.
Output: Length of Longest Positive Subsequence is 2
```

## Time Complexity Analysis:

The time complexity of the longestPositiveSequence function is O(2^N), where N is the size of the input array. This is because the function explores all possible subsequence combinations, resulting in an exponential time complexity.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.