Skip to main content

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[0]);

    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[0]);

    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)
    {
        Subsequence task = new Subsequence();
        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;
        task.printData(arr1, size);
        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;;
        task.printData(arr2, size);
        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()
{
	Subsequence task = Subsequence();
	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[0]);
	task.printData(arr1, size);
	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[0]);;
	task.printData(arr2, size);
	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)
	{
		Subsequence task = new Subsequence();
		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;
		task.printData(arr1, size);
		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;;
		task.printData(arr2, size);
		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()
{
	$task = new Subsequence();
	$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);
	$task->printData($arr1, $size);
	$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);;
	$task->printData($arr2, $size);
	$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 task = new Subsequence();
	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;
	task.printData(arr1, size);
	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;;
	task.printData(arr2, size);
	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() :
	task = Subsequence()
	arr1 = [-4, 5, 1, -2, -7, 3, -4]
	arr2 = [-6, 2, 2, -1]
	#  Get the number of element in array
	size = len(arr1)
	task.printData(arr1, size)
	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)
	task.printData(arr2, size)
	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() 
	task = Subsequence.new()
	arr1 = [-4, 5, 1, -2, -7, 3, -4]
	arr2 = [-6, 2, 2, -1]
	#  Get the number of element in array
	size = arr1.length
	task.printData(arr1, size)
	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
	task.printData(arr2, size)
	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;
		task.printData(arr1, size);
		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;;
		task.printData(arr2, size);
		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 task: Subsequence = Subsequence();
	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;
	task.printData(arr1, size);
	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;
	task.printData(arr2, size);
	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.

Last updated on by Kalkicode




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.

New Comment