http://www.geeksforgeeks.org/count-strictly-increasing-subarrays/
Given an array of integers, count number of subarrays (of size more than one) that are strictly increasing.
Given an array of integers, count number of subarrays (of size more than one) that are strictly increasing.
Input: arr[] = {1, 2, 3, 4}
Output: 6
There are 6 subarrays {1, 2}, {1, 2, 3}, {1, 2, 3, 4}
{2, 3}, {2, 3, 4} and {3, 4}
A Simple Solution is to generate all possible subarrays, and for every subarray check if subarray is strictly increasing or not. Worst case time complexity of this solution would be O(n3).
A Better Solution is to use the fact that if subarray arr[i:j] is not strictly increasing, then subarrays arr[i:j+1], arr[i:j+2], .. arr[i:n-1] cannot be strictly increasing.
int countIncreasing(int arr[], int n){ // Initialize count of subarrays as 0 int cnt = 0; // Pick starting point for (int i=0; i<n; i++) { // Pick ending point for (int j=i+1; j<n; j++) { if (arr[j] > arr[j-1]) cnt++; // If subarray arr[i..j] is not strictly // increasing, then subarrays after it , i.e., // arr[i..j+1], arr[i..j+2], .... cannot // be strictly increasing else break; } } return cnt;}
Time complexity of the above solution is O(m) where m is number of subarrays in output
An Efficient Solution can count subarrays in O(n) time. The idea is based on fact that a sorted sunarray of length ‘len’ adds len*(len-1)/2 to result. For example, {10, 20, 30, 40} adds 6 to the result.
int countIncreasing(int arr[], int n){ int cnt = 0; // Initialize result // Initialize length of current increasing // subarray int len = 1; // Traverse through the array for (int i=0; i < n-1; ++i) { // If arr[i+1] is greater than arr[i], // then increment length if (arr[i + 1] > arr[i]) len++; // Else Update count and reset length else { cnt += (((len - 1) * len) / 2); len = 1; } } // If length is more than 1 if (len > 1) cnt += (((len - 1) * len) / 2); return cnt;}