считать непрерывный подмассив, начинающийся с этого индекса

У меня есть массив A, и мне нужен массив B того же размера, что и A, где B[i] представляет собой длину непрерывного подмассива, начинающегося с A[i], в котором все элементы меньше или равны A[i]

Пример

A={1,3,4,2,4,5,1,6}

Вывод

B={1,1,3,1,1,2,1,1}

Пояснение:

Для A[2]=4 есть подмассив с элементом{4,2,4}, для A[5]=5 есть подмассив {5,1} для A[7]=6 есть подмассив {6}


arrays algorithm maxlength sub-array
person raju varshney    schedule 12.08.2015    source источник
comment
Не могу найти ни одного вопроса.   -  person vdolez    schedule 12.08.2015
comment
Похоже, вы скопировали домашнее задание и хотите получить ответ, который можно было бы скопировать и отправить в качестве домашнего задания. Такие вопросы здесь не очень приветствуются. Попробуйте добавить, что вы пробовали и почему это не удалось. Кроме того, я решил эту проблему как подзадачу в этом ответе.   -  person kajacx    schedule 12.08.2015

Ответы (1)


arrow_upward
0
arrow_downward

Сложность: O(n)

#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], after[max]={0};
    input >> n;
    for (int i=0; i<n; i++)
        input >> arr[i];

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


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

    return 0;
}
person hasan    schedule 16.08.2015