数组元素为最大的相邻子数组个数

Question

有没有一种方法可以在小于O(n^2)的时间内做到这一点。

O（nlogn）还是O(n)？

Example-
If array is {1,2,3}. Then-
For '1': 1 Such subarray {1}.
For '2': 2 Such subarrays {2},{1,2}
For '3': 3 Such subarrays {3},{2,3},{1,2,3}

Answer 1

我很难用语言解释我的解决方案。我只会添加代码。它会自己解释：

#include <iostream>
#include <fstream>
using namespace std;

#define max 10000

int main(int argc, const char * argv[]) {

    ifstream input("/Users/appleuser/Documents/Developer/xcode projects/SubArrayCount/SubArrayCount/input.in");

    int n, arr[max], before[max]={0}, after[max]={0}, result[max];
    input >> n;
    for (int i=0; i<n; i++)
        input >> arr[i];

    for (int i=0;i<n;i++)
        for (int j=i-1;j>=0&&arr[j]<arr[i];j-=before[j]+1)
            before[i]+=before[j]+1;

    for (int i=n-1;i>=0;i--)
        for (int j=i+1;j<n&&arr[j]<arr[i];j+=after[j]+1)
            after[i]+=after[j]+1;

    for (int i=0;i<n;i++)
        result[i]= (before[i]+1)*(after[i]+1);

    for (int i=0; i<n; i++)
        cout << result [i] << " ";
    cout << endl;

    return 0;
}

对([i]+1)*([i]+1):

对于每一个值，我们需要的数字位于该值之前且小于该值，数字位于该值之后且小于该值。

  | 0  1  2  3  4  5 .... count of numbers less than the value and appears before.
---------------------
0 | 1  2  3  4  5  6
1 | 2  4  6  8  10 12
2 | 3  6  9  12 15 18
3 | 4  8  12 16 20 24
4 | 5  10 15 20 25 30
5 | 6  12 18 24 30 36
. | 
. |
. |
count of numbers less than the value and appears after.