Максимальная сумма подмассива по модулю - PullRequest
Новая
       81

Максимальная сумма подмассива по модулю

0 голосов
/ 09 мая 2020

Это вопрос в разделе практики хакерского ранга.

Дан массив из n элементов и целое число m. Задача состоит в том, чтобы найти максимальное значение суммы его подмассива по модулю m, т.е. найти сумму каждого подмассива по модулю m и вывести максимальное значение этой операции по модулю.

Входные данные: arr[] = { 3, 3, 9, 9, 5 } и m = 7 Вывод: 6

для подмассива [3,3], сумма = 6. сумма% m = 6.

До сих пор я пытался отслеживать максимальную сумму по модулю, arr[] = 3,3,9,9,5 max_so_far = 3,6,1,3,1. затем возвращает максимальное значение массива max_so_far. Этот код работает только для некоторых тестовых случаев. 

long maximumSum(vector<long> a, long m) {
    int s=a.size();
    vector<long> msf(s);//, max_idx(S);
    msf[0]=a[0];
    long long res=a[0];
    //max_idx[0]=0
    for(int i=1;i<s;i++){
        msf[i] = max((msf[i-1]+a[i])%m , a[i]%m);

    }
    return *max_element(msf.begin() , msf.end());
}

где вектор a - это входной вектор.

Может ли кто-нибудь сказать мне, что не так в моем коде ??

...