Skip to main content

Find the length of largest subsequence with positive sum

Here given code implementation process.

/*
    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
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