Skip to main content

Count strictly increasing subarrays by using dynamic programming

In this article, we will explore the problem of counting strictly increasing subarrays in an array using dynamic programming. We will begin by understanding the problem statement and then proceed to explain a solution using dynamic programming techniques. We will provide a detailed explanation of the code implementation in C and analyze the output for a couple of test cases. Let's dive in!

Problem Statement:

Given an array of integers, we need to count the number of strictly increasing subarrays. A subarray is defined as a contiguous sequence of elements in the array. A subarray is considered strictly increasing if each element is strictly greater than its previous element.

Solution Using Dynamic Programming:

To solve this problem efficiently, we can use dynamic programming. We will maintain an array called 'dp' of the same size as the input array, initialized with all elements set to zero. The 'dp' array will store the count of increasing subarrays ending at each index.

We will iterate through the input array from left to right, starting from the second element. At each index, we compare the current element with the previous element. If the current element is greater than the previous element, it means an increasing subarray is formed. We update the 'dp' array at that index by adding 1 to the 'dp' value at the previous index. This signifies the count of increasing subarrays ending at the current index.

Simultaneously, we maintain a counter variable 'count' to keep track of the total count of increasing subarrays. Whenever we update the 'dp' array, we increment the 'count' variable by the new 'dp' value at the current index. By the end of the iteration, the 'count' variable will store the total count of increasing subarrays in the input array.

Code Solution

// C Program
// Count strictly increasing subarrays by using dynamic programming
#include <stdio.h>

// Display array elements
void printArr(int arr[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("  %d", arr[i]);
	}
	printf("\n");
}
void countIncreasingArr(int arr[], int n)
{
	int count = 0;
	int dp[n];
	for (int i = 0; i < n; ++i)
	{
		dp[i] = 0;
	}
	for (int i = 1; i < n; ++i)
	{
		if (arr[i - 1] < arr[i])
		{
			// When increasing subarray occurs
			dp[i] = dp[i - 1] + 1;
			// Add counter
			count += dp[i];
		}
	}
	printArr(arr, n);
	// Display calculated result
	printf(" Increasing subarrays : %d \n", count);
}
int main()
{
	// Arrays
	int a[] = {
		1 , 2 , 5 , 7 , 1 , 3 , 4
	};
	int b[] = {
		1 , 3 , 2 , 7 , 7 , 1 , 4 , 6
	};
	// Get the size
	int l1 = sizeof(a) / sizeof(a[0]);
	int l2 = sizeof(b) / sizeof(b[0]);
	// Test A
	/*
	    arr = [1, 2, 5, 7, 1, 3, 4]
	    ------------------------------
	    1)  [1, 2]
	    2)  [1, 2, 5]
	    3)  [2, 5]
	    4)  [1, 2, 5, 7]
	    5)  [2, 5, 7]
	    6)  [5, 7]
	    7)  [1, 3]
	    8)  [1, 3, 4]
	    9)  [3, 4]
	*/
	countIncreasingArr(a, l1);
	// Test B
	/*
	    arr = [1, 3, 2, 7,7, 1, 4, 6]
	    ------------------------------
	    1)  [1, 3]
	    2)  [2, 7]
	    3)  [1, 4]
	    4)  [1, 4, 6]
	    5)  [4, 6]
	*/
	countIncreasingArr(b, l2);
	return 0;
}

Output

  1  2  5  7  1  3  4
 Increasing subarrays : 9
  1  3  2  7  7  1  4  6
 Increasing subarrays : 5
/*
    Java Program
    Count strictly increasing subarrays by using dynamic programming
*/
public class Subarrays
{
	// Display array elements
	public void printArr(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	public void countIncreasingArr(int[] arr, int n)
	{
		int count = 0;
		int[] dp = new int[n];
		for (int i = 0; i < n; ++i)
		{
			dp[i] = 0;
		}
		for (int i = 1; i < n; ++i)
		{
			if (arr[i - 1] < arr[i])
			{
				// When increasing subarray occurs
				dp[i] = dp[i - 1] + 1;
				// Add counter
				count += dp[i];
			}
		}
		printArr(arr, n);
		// Display calculated result
		System.out.print(" Increasing subarrays : " + count + " \n");
	}
	public static void main(String[] args)
	{
		Subarrays task = new Subarrays();
		int[] a = {
			1 , 2 , 5 , 7 , 1 , 3 , 4
		};
		int[] b = {
			1 , 3 , 2 , 7 , 7 , 1 , 4 , 6
		};
		// Get the size
		int l1 =  a.length;
		int l2 =  b.length;
		// Test A
		/*
		    arr = [1, 2, 5, 7, 1, 3, 4]
		    ------------------------------
		    1)  [1, 2]
		    2)  [1, 2, 5]
		    3)  [2, 5]
		    4)  [1, 2, 5, 7]
		    5)  [2, 5, 7]
		    6)  [5, 7]
		    7)  [1, 3]
		    8)  [1, 3, 4]
		    9)  [3, 4]
		    -----------
		    Result = 9
		*/
		task.countIncreasingArr(a, l1);
		// Test B
		/*
		    arr = [1, 3, 2, 7,7, 1, 4, 6]
		    ------------------------------
		    1)  [1, 3]
		    2)  [2, 7]
		    3)  [1, 4]
		    4)  [1, 4, 6]
		    5)  [4, 6]
		    -----------
		    Result = 5
		*/
		task.countIncreasingArr(b, l2);
	}
}

Output

 1 2 5 7 1 3 4
 Increasing subarrays : 9
 1 3 2 7 7 1 4 6
 Increasing subarrays : 5
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program
    Count strictly increasing subarrays by using dynamic programming
*/
class Subarrays
{
	public:
		// Display array elements
		void printArr(int arr[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	void countIncreasingArr(int arr[], int n)
	{
		int count = 0;
		int dp[n];
		for (int i = 0; i < n; ++i)
		{
			dp[i] = 0;
		}
		for (int i = 1; i < n; ++i)
		{
			if (arr[i - 1] < arr[i])
			{
				// When increasing subarray occurs
				dp[i] = dp[i - 1] + 1;
				// Add counter
				count += dp[i];
			}
		}
		this->printArr(arr, n);
		// Display calculated result
		cout << " Increasing subarrays : " << count << " \n";
	}
};
int main()
{
	Subarrays *task = new Subarrays();
	int a[] = {
		1 , 2 , 5 , 7 , 1 , 3 , 4
	};
	int b[] = {
		1 , 3 , 2 , 7 , 7 , 1 , 4 , 6
	};
	// Get the size
	int l1 = sizeof(a) / sizeof(a[0]);
	int l2 = sizeof(b) / sizeof(b[0]);
	// Test A
	/*
	    arr = [1, 2, 5, 7, 1, 3, 4]
	    ------------------------------
	    1)  [1, 2]
	    2)  [1, 2, 5]
	    3)  [2, 5]
	    4)  [1, 2, 5, 7]
	    5)  [2, 5, 7]
	    6)  [5, 7]
	    7)  [1, 3]
	    8)  [1, 3, 4]
	    9)  [3, 4]
	    -----------
	    Result = 9
	*/
	task->countIncreasingArr(a, l1);
	// Test B
	/*
	    arr = [1, 3, 2, 7,7, 1, 4, 6]
	    ------------------------------
	    1)  [1, 3]
	    2)  [2, 7]
	    3)  [1, 4]
	    4)  [1, 4, 6]
	    5)  [4, 6]
	    -----------
	    Result = 5
	*/
	task->countIncreasingArr(b, l2);
	return 0;
}

Output

 1 2 5 7 1 3 4
 Increasing subarrays : 9
 1 3 2 7 7 1 4 6
 Increasing subarrays : 5
// Include namespace system
using System;
/*
    Csharp Program
    Count strictly increasing subarrays by using dynamic programming
*/
public class Subarrays
{
	// Display array elements
	public void printArr(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	public void countIncreasingArr(int[] arr, int n)
	{
		int count = 0;
		int[] dp = new int[n];
		for (int i = 0; i < n; ++i)
		{
			dp[i] = 0;
		}
		for (int i = 1; i < n; ++i)
		{
			if (arr[i - 1] < arr[i])
			{
				// When increasing subarray occurs
				dp[i] = dp[i - 1] + 1;
				// Add counter
				count += dp[i];
			}
		}
		this.printArr(arr, n);
		// Display calculated result
		Console.Write(" Increasing subarrays : " + count + " \n");
	}
	public static void Main(String[] args)
	{
		Subarrays task = new Subarrays();
		int[] a = {
			1 , 2 , 5 , 7 , 1 , 3 , 4
		};
		int[] b = {
			1 , 3 , 2 , 7 , 7 , 1 , 4 , 6
		};
		// Get the size
		int l1 = a.Length;
		int l2 = b.Length;
		// Test A
		/*
		    arr = [1, 2, 5, 7, 1, 3, 4]
		    ------------------------------
		    1)  [1, 2]
		    2)  [1, 2, 5]
		    3)  [2, 5]
		    4)  [1, 2, 5, 7]
		    5)  [2, 5, 7]
		    6)  [5, 7]
		    7)  [1, 3]
		    8)  [1, 3, 4]
		    9)  [3, 4]
		    -----------
		    Result = 9
		*/
		task.countIncreasingArr(a, l1);
		// Test B
		/*
		    arr = [1, 3, 2, 7,7, 1, 4, 6]
		    ------------------------------
		    1)  [1, 3]
		    2)  [2, 7]
		    3)  [1, 4]
		    4)  [1, 4, 6]
		    5)  [4, 6]
		    -----------
		    Result = 5
		*/
		task.countIncreasingArr(b, l2);
	}
}

Output

 1 2 5 7 1 3 4
 Increasing subarrays : 9
 1 3 2 7 7 1 4 6
 Increasing subarrays : 5
package main
import "fmt"
/*
    Go Program
    Count strictly increasing subarrays by using dynamic programming
*/

// Display array elements
func printArr(arr[] int, n int) {
	for i := 0 ; i < n ; i++ {
		fmt.Print(" ", arr[i])
	}
	fmt.Print("\n")
}
func countIncreasingArr(arr[] int, n int) {
	var count int = 0
	var dp = make([] int, n)
	for i := 1 ; i < n ; i++ {
		if arr[i - 1] < arr[i] {
			// When increasing subarray occurs
			dp[i] = dp[i - 1] + 1
			// Add counter
			count += dp[i]
		}
	}
	printArr(arr, n)
	// Display calculated result
	fmt.Print(" Increasing subarrays : ", count, " \n")
}
func main() {

	var a = [] int {
		1,
		2,
		5,
		7,
		1,
		3,
		4,
	}
	var b = [] int {
		1,
		3,
		2,
		7,
		7,
		1,
		4,
		6,
	}
	// Get the size
	var l1 int = len(a)
	var l2 int = len(b)
	// Test A
	/*
	    arr = [1, 2, 5, 7, 1, 3, 4]
	    ------------------------------
	    1)  [1, 2]
	    2)  [1, 2, 5]
	    3)  [2, 5]
	    4)  [1, 2, 5, 7]
	    5)  [2, 5, 7]
	    6)  [5, 7]
	    7)  [1, 3]
	    8)  [1, 3, 4]
	    9)  [3, 4]
	    -----------
	    Result = 9
	*/
	countIncreasingArr(a, l1)
	// Test B
	/*
	    arr = [1, 3, 2, 7,7, 1, 4, 6]
	    ------------------------------
	    1)  [1, 3]
	    2)  [2, 7]
	    3)  [1, 4]
	    4)  [1, 4, 6]
	    5)  [4, 6]
	    -----------
	    Result = 5
	*/
	countIncreasingArr(b, l2)
}

Output

 1 2 5 7 1 3 4
 Increasing subarrays : 9
 1 3 2 7 7 1 4 6
 Increasing subarrays : 5
<?php
/*
    Php Program
    Count strictly increasing subarrays by using dynamic programming
*/
class Subarrays
{
	// Display array elements
	public	function printArr($arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo(" ".$arr[$i]);
		}
		echo("\n");
	}
	public	function countIncreasingArr($arr, $n)
	{
		$count = 0;
		$dp = array_fill(0, $n, 0);
		for ($i = 1; $i < $n; ++$i)
		{
			if ($arr[$i - 1] < $arr[$i])
			{
				// When increasing subarray occurs
				$dp[$i] = $dp[$i - 1] + 1;
				// Add counter
				$count += $dp[$i];
			}
		}
		$this->printArr($arr, $n);
		// Display calculated result
		echo(" Increasing subarrays : ".$count." \n");
	}
}

function main()
{
	$task = new Subarrays();
	$a = array(1, 2, 5, 7, 1, 3, 4);
	$b = array(1, 3, 2, 7, 7, 1, 4, 6);
	// Get the size
	$l1 = count($a);
	$l2 = count($b);
	// Test A
	/*
	    arr = [1, 2, 5, 7, 1, 3, 4]
	    ------------------------------
	    1)  [1, 2]
	    2)  [1, 2, 5]
	    3)  [2, 5]
	    4)  [1, 2, 5, 7]
	    5)  [2, 5, 7]
	    6)  [5, 7]
	    7)  [1, 3]
	    8)  [1, 3, 4]
	    9)  [3, 4]
	    -----------
	    Result = 9
	*/
	$task->countIncreasingArr($a, $l1);
	// Test B
	/*
	    arr = [1, 3, 2, 7,7, 1, 4, 6]
	    ------------------------------
	    1)  [1, 3]
	    2)  [2, 7]
	    3)  [1, 4]
	    4)  [1, 4, 6]
	    5)  [4, 6]
	    -----------
	    Result = 5
	*/
	$task->countIncreasingArr($b, $l2);
}
main();

Output

 1 2 5 7 1 3 4
 Increasing subarrays : 9
 1 3 2 7 7 1 4 6
 Increasing subarrays : 5
/*
    Node JS Program
    Count strictly increasing subarrays by using dynamic programming
*/
class Subarrays
{
	// Display array elements
	printArr(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	countIncreasingArr(arr, n)
	{
		var count = 0;
		var dp = Array(n).fill(0);
		for (var i = 1; i < n; ++i)
		{
			if (arr[i - 1] < arr[i])
			{
				// When increasing subarray occurs
				dp[i] = dp[i - 1] + 1;
				// Add counter
				count += dp[i];
			}
		}
		this.printArr(arr, n);
		// Display calculated result
		process.stdout.write(" Increasing subarrays : " + count + " \n");
	}
}

function main()
{
	var task = new Subarrays();
	var a = [1, 2, 5, 7, 1, 3, 4];
	var b = [1, 3, 2, 7, 7, 1, 4, 6];
	// Get the size
	var l1 = a.length;
	var l2 = b.length;
	// Test A
	/*
	    arr = [1, 2, 5, 7, 1, 3, 4]
	    ------------------------------
	    1)  [1, 2]
	    2)  [1, 2, 5]
	    3)  [2, 5]
	    4)  [1, 2, 5, 7]
	    5)  [2, 5, 7]
	    6)  [5, 7]
	    7)  [1, 3]
	    8)  [1, 3, 4]
	    9)  [3, 4]
	    -----------
	    Result = 9
	*/
	task.countIncreasingArr(a, l1);
	// Test B
	/*
	    arr = [1, 3, 2, 7,7, 1, 4, 6]
	    ------------------------------
	    1)  [1, 3]
	    2)  [2, 7]
	    3)  [1, 4]
	    4)  [1, 4, 6]
	    5)  [4, 6]
	    -----------
	    Result = 5
	*/
	task.countIncreasingArr(b, l2);
}
main();

Output

 1 2 5 7 1 3 4
 Increasing subarrays : 9
 1 3 2 7 7 1 4 6
 Increasing subarrays : 5
#    Python 3 Program
#    Count strictly increasing subarrays by using dynamic programming
class Subarrays :
	#  Display list elements
	def printArr(self, arr, n) :
		i = 0
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
		print(end = "\n")
	
	def countIncreasingArr(self, arr, n) :
		count = 0
		dp = [0] * (n)
		i = 1
		while (i < n) :
			if (arr[i - 1] < arr[i]) :
				#  When increasing sublist occurs
				dp[i] = dp[i - 1] + 1
				#  Add counter
				count += dp[i]
			
			i += 1
		
		self.printArr(arr, n)
		#  Display calculated result
		print(" Increasing subarrays : ", count ," ")
	

def main() :
	task = Subarrays()
	a = [1, 2, 5, 7, 1, 3, 4]
	b = [1, 3, 2, 7, 7, 1, 4, 6]
	#  Get the size
	l1 = len(a)
	l2 = len(b)
	#  Test A
	#    arr = [1, 2, 5, 7, 1, 3, 4]
	#    ------------------------------
	#    1)  [1, 2]
	#    2)  [1, 2, 5]
	#    3)  [2, 5]
	#    4)  [1, 2, 5, 7]
	#    5)  [2, 5, 7]
	#    6)  [5, 7]
	#    7)  [1, 3]
	#    8)  [1, 3, 4]
	#    9)  [3, 4]
	#    -----------
	#    Result = 9
	task.countIncreasingArr(a, l1)
	#  Test B
	#    arr = [1, 3, 2, 7,7, 1, 4, 6]
	#    ------------------------------
	#    1)  [1, 3]
	#    2)  [2, 7]
	#    3)  [1, 4]
	#    4)  [1, 4, 6]
	#    5)  [4, 6]
	#    -----------
	#    Result = 5
	task.countIncreasingArr(b, l2)

if __name__ == "__main__": main()

Output

  1  2  5  7  1  3  4
 Increasing subarrays :  9
  1  3  2  7  7  1  4  6
 Increasing subarrays :  5
#    Ruby Program
#    Count strictly increasing subarrays by using dynamic programming
class Subarrays 
	#  Display array elements
	def printArr(arr, n) 
		i = 0
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

		print("\n")
	end

	def countIncreasingArr(arr, n) 
		count = 0
		dp = Array.new(n) {0}
		i = 1
		while (i < n) 
			if (arr[i - 1] < arr[i]) 
				#  When increasing subarray occurs
				dp[i] = dp[i - 1] + 1
				#  Add counter
				count += dp[i]
			end

			i += 1
		end

		self.printArr(arr, n)
		#  Display calculated result
		print(" Increasing subarrays : ", count ," \n")
	end

end

def main() 
	task = Subarrays.new()
	a = [1, 2, 5, 7, 1, 3, 4]
	b = [1, 3, 2, 7, 7, 1, 4, 6]
	#  Get the size
	l1 = a.length
	l2 = b.length
	#  Test A
	#    arr = [1, 2, 5, 7, 1, 3, 4]
	#    ------------------------------
	#    1)  [1, 2]
	#    2)  [1, 2, 5]
	#    3)  [2, 5]
	#    4)  [1, 2, 5, 7]
	#    5)  [2, 5, 7]
	#    6)  [5, 7]
	#    7)  [1, 3]
	#    8)  [1, 3, 4]
	#    9)  [3, 4]
	#    -----------
	#    Result = 9
	task.countIncreasingArr(a, l1)
	#  Test B
	#    arr = [1, 3, 2, 7,7, 1, 4, 6]
	#    ------------------------------
	#    1)  [1, 3]
	#    2)  [2, 7]
	#    3)  [1, 4]
	#    4)  [1, 4, 6]
	#    5)  [4, 6]
	#    -----------
	#    Result = 5
	task.countIncreasingArr(b, l2)
end

main()

Output

 1 2 5 7 1 3 4
 Increasing subarrays : 9 
 1 3 2 7 7 1 4 6
 Increasing subarrays : 5 
/*
    Scala Program
    Count strictly increasing subarrays by using dynamic programming
*/
class Subarrays()
{
	// Display array elements
	def printArr(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	def countIncreasingArr(arr: Array[Int], n: Int): Unit = {
		var count: Int = 0;
		var dp: Array[Int] = Array.fill[Int](n)(0);
		var i: Int = 1;
		while (i < n)
		{
			if (arr(i - 1) < arr(i))
			{
				// When increasing subarray occurs
				dp(i) = dp(i - 1) + 1;
				// Add counter
				count += dp(i);
			}
			i += 1;
		}
		printArr(arr, n);
		// Display calculated result
		print(" Increasing subarrays : " + count + " \n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subarrays = new Subarrays();
		var a: Array[Int] = Array(1, 2, 5, 7, 1, 3, 4);
		var b: Array[Int] = Array(1, 3, 2, 7, 7, 1, 4, 6);
		// Get the size
		var l1: Int = a.length;
		var l2: Int = b.length;
		// Test A
		/*
		    arr = [1, 2, 5, 7, 1, 3, 4]
		    ------------------------------
		    1)  [1, 2]
		    2)  [1, 2, 5]
		    3)  [2, 5]
		    4)  [1, 2, 5, 7]
		    5)  [2, 5, 7]
		    6)  [5, 7]
		    7)  [1, 3]
		    8)  [1, 3, 4]
		    9)  [3, 4]
		    -----------
		    Result = 9
		*/
		task.countIncreasingArr(a, l1);
		// Test B
		/*
		    arr = [1, 3, 2, 7,7, 1, 4, 6]
		    ------------------------------
		    1)  [1, 3]
		    2)  [2, 7]
		    3)  [1, 4]
		    4)  [1, 4, 6]
		    5)  [4, 6]
		    -----------
		    Result = 5
		*/
		task.countIncreasingArr(b, l2);
	}
}

Output

 1 2 5 7 1 3 4
 Increasing subarrays : 9
 1 3 2 7 7 1 4 6
 Increasing subarrays : 5
import Foundation;
/*
    Swift 4 Program
    Count strictly increasing subarrays by using dynamic programming
*/
class Subarrays
{
	// Display array elements
	func printArr(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	func countIncreasingArr(_ arr: [Int], _ n: Int)
	{
		var count: Int = 0;
		var dp: [Int] = Array(repeating: 0, count: n);
		var i: Int = 1;
		while (i < n)
		{
			if (arr[i - 1] < arr[i])
			{
				// When increasing subarray occurs
				dp[i] = dp[i - 1] + 1;
				// Add counter
				count += dp[i];
			}
			i += 1;
		}
		self.printArr(arr, n);
		// Display calculated result
		print(" Increasing subarrays : ", count ," ");
	}
}
func main()
{
	let task: Subarrays = Subarrays();
	let a: [Int] = [1, 2, 5, 7, 1, 3, 4];
	let b: [Int] = [1, 3, 2, 7, 7, 1, 4, 6];
	// Get the size
	let l1: Int = a.count;
	let l2: Int = b.count;
	// Test A
	/*
	    arr = [1, 2, 5, 7, 1, 3, 4]
	    ------------------------------
	    1)  [1, 2]
	    2)  [1, 2, 5]
	    3)  [2, 5]
	    4)  [1, 2, 5, 7]
	    5)  [2, 5, 7]
	    6)  [5, 7]
	    7)  [1, 3]
	    8)  [1, 3, 4]
	    9)  [3, 4]
	    -----------
	    Result = 9
	*/
	task.countIncreasingArr(a, l1);
	// Test B
	/*
	    arr = [1, 3, 2, 7,7, 1, 4, 6]
	    ------------------------------
	    1)  [1, 3]
	    2)  [2, 7]
	    3)  [1, 4]
	    4)  [1, 4, 6]
	    5)  [4, 6]
	    -----------
	    Result = 5
	*/
	task.countIncreasingArr(b, l2);
}
main();

Output

  1  2  5  7  1  3  4
 Increasing subarrays :  9
  1  3  2  7  7  1  4  6
 Increasing subarrays :  5
/*
    Kotlin Program
    Count strictly increasing subarrays by using dynamic programming
*/
class Subarrays
{
	// Display array elements
	fun printArr(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr[i]);
			i += 1;
		}
		print("\n");
	}
	fun countIncreasingArr(arr: Array < Int > , n: Int): Unit
	{
		var count: Int = 0;
		var dp: Array < Int > = Array(n)
		{
			0
		};
		var i: Int = 1;
		while (i < n)
		{
			if (arr[i - 1] < arr[i])
			{
				// When increasing subarray occurs
				dp[i] = dp[i - 1] + 1;
				// Add counter
				count += dp[i];
			}
			i += 1;
		}
		this.printArr(arr, n);
		// Display calculated result
		print(" Increasing subarrays : " + count + " \n");
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subarrays = Subarrays();
	val a: Array < Int > = arrayOf(1, 2, 5, 7, 1, 3, 4);
	val b: Array < Int > = arrayOf(1, 3, 2, 7, 7, 1, 4, 6);
	// Get the size
	val l1: Int = a.count();
	val l2: Int = b.count();
	// Test A
	/*
	    arr = [1, 2, 5, 7, 1, 3, 4]
	    ------------------------------
	    1)  [1, 2]
	    2)  [1, 2, 5]
	    3)  [2, 5]
	    4)  [1, 2, 5, 7]
	    5)  [2, 5, 7]
	    6)  [5, 7]
	    7)  [1, 3]
	    8)  [1, 3, 4]
	    9)  [3, 4]
	    -----------
	    Result = 9
	*/
	task.countIncreasingArr(a, l1);
	// Test B
	/*
	    arr = [1, 3, 2, 7,7, 1, 4, 6]
	    ------------------------------
	    1)  [1, 3]
	    2)  [2, 7]
	    3)  [1, 4]
	    4)  [1, 4, 6]
	    5)  [4, 6]
	    -----------
	    Result = 5
	*/
	task.countIncreasingArr(b, l2);
}

Output

 1 2 5 7 1 3 4
 Increasing subarrays : 9
 1 3 2 7 7 1 4 6
 Increasing subarrays : 5

Code Implementation:

The provided C code implements the solution using the dynamic programming approach. It defines a function 'printArr' to display the elements of an array and a function 'countIncreasingArr' to calculate and display the count of increasing subarrays.

Inside the 'countIncreasingArr' function, the 'dp' array is initialized with zeros. Then, using a loop, the input array is traversed to identify and count the strictly increasing subarrays. Finally, the input array and the count of increasing subarrays are printed as output.

Example Test Cases:

The code includes two example test cases, 'a' and 'b', each represented by an array. Let's analyze the output for these test cases.

Test Case A: Input Array: [1, 2, 5, 7, 1, 3, 4] The increasing subarrays are:

  1. [1, 2]
  2. [1, 2, 5]
  3. [2, 5]
  4. [1, 2, 5, 7]
  5. [2, 5, 7]
  6. [5, 7]
  7. [1, 3]
  8. [1, 3, 4]
  9. [3, 4]
Output:
    1 2 5 7 1 3 4
    Increasing subarrays: 9

Test Case B:

Input Array: [1, 3, 2, 7, 7, 1, 4, 6]
    The increasing subarrays are:
  1. [1, 3]
  2. [2, 7]
  3. [1, 4]
  4. [1, 4, 6]
  5. [4, 6]
 Output:
    1 3 2 7 7 1 4 6
    Increasing subarrays: 5

We discussed the problem of counting strictly increasing subarrays using dynamic programming. We explained the solution approach and provided a step-by-step explanation of the code implementation in C. We also analyzed the output for two example test cases to demonstrate the correctness of the solution. By employing dynamic programming techniques, we can efficiently solve problems like this and obtain the desired results.





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