# 計算嚴格增加的子數組 > 原文： [https://www.geeksforgeeks.org/count-strictly-increasing-subarrays/](https://www.geeksforgeeks.org/count-strictly-increasing-subarrays/) 給定一個整數數組，[子數組](https://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/)（大小大于 1）的計數嚴格增加。 預期時間復雜度：`O(n)` 預期額外空間：`O(1)` 例子： ``` Input: arr[] = {1, 4, 3} Output: 1 There is only one subarray {1, 4} 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} Input: arr[] = {1, 2, 2, 4} Output: 2 There are 2 subarrays {1, 2} and {2, 4} ``` [](https://practice.geeksforgeeks.org/problem-page.php?pid=405) ## 強烈建議您在繼續解決方案之前，單擊此處進行練習。 **簡單解決方案**是[生成所有可能的子數組](https://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/)，并針對每個子數組檢查子數組是否嚴格增加。 該解決方案的最壞情況下時間復雜度將為`O(n^3)`。 **更好的解決方案**使用以下事實：如果子數組`arr [i: j]`沒有嚴格增加，則子數組`arr[i: j + 1], arr[i: j + 2], .. arr[i: n-1]`不能嚴格增加。 下面是基于上述思想的程序。 ## C++ ```cpp // C++ program to count number of strictly // increasing subarrays #include<bits/stdc++.h> using namespace std; 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; } // Driver program int main() { ??int arr[] = {1, 2, 2, 4}; ??int n = sizeof(arr)/sizeof(arr[0]); ??cout << "Count of strictly increasing subarrays is " ???????<< countIncreasing(arr, n); ??return 0; } ```