# Number of strictly increasing subarrays

## Given an array, this function will find the number of strictly increasing subarrays. This can be clearly explained in below example

### Example

Input :
arr[] = {4, 8, 7, 10, 11}

Output :
4
The input array has 4 strictly increasing subarrays ie, {4, 8}, {7, 10}, {7, 10, 11}, {10, 11}

Time Complexity:O( ),

where m is the number of subarrays in the output.

This method will use the fact that if the subarray arr[i,j] is  not strictly increasing then arr[i,j+1], arr[i,j+2], ...., arr[i,n-1] cannot be strictly increasing

## Algorithm

1. Simply create two loops

2. In the outer loop select an element till end of the array. ie, i=0 to n-1, where n is the size

3. In the inner loop select an element from i+1 to n-1. ie, j=i+1 to n-1

4. Check if the array is increasing ie, arr[j]>arr[j-1]. If it is increasing, increment the count of number of subarrays strictly increasing by 1.

5. else, break the inner loop.

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

int incSubarray(int arr[], int n) //this function returns the number of strictly inc subarrays
{
int count = 0;
for (int i = 0; i < n; ++i)
{
for (int j = i+1; j < n; ++j)
{
if(arr[j]>arr[j-1]) //if it is inc, increment the count
{
count++;
}
else
{
break; //if it is not strictly inc, break
}
}
}
return count;
}
int main()
{
int arr[]= {4,8,7,10,11};  //creating an array
int n = sizeof(arr)/sizeof(arr[0]); //size of the array
cout<<"Number of strictly increasing subarrays are "<<incSubarray(arr, n);
return 0;
}``````

Time Complexity : O(n)

In this method, we will use the fact that the sorted array of length l will have (l)*(l-1)/2 strictly increasing subarrays

## Algorithm

1. Initialize count to 0 and length to 1.

2. Till end of the array

3. If the array is increasing ie, arr[i+1]>arr[i], then increment the length by 1. else, increment count by (length)(length-1)/2 and make length =1.

4. After traversing the array, if the length is greater than 1, then increment count by (length)(length-1)/2.

5. return count.

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

int incSubarray(int arr[], int n) //this function returns the number of strictly inc subarrays
{
int count = 0;
int length = 1;
for (int i = 0; i < n; ++i)
{
if(arr[i+1] > arr[i])
{
length++;
}
else
{
count = count + (length)*(length -1)/2;
length = 1;
}
}
return count;
}
int main()
{
int arr[]= {4,8,7,10,11};  //creating an array
int n = sizeof(arr)/sizeof(arr[0]); //size of the array
cout<<"Number of strictly increasing subarrays are "<<incSubarray(arr, n);
return 0;
}``````

Scroll to Top