Как реализовать скользящее окно на js?

302

14 февраля 2018, 13:15

Я пытаюсь решить логическую задачу на js:

На красивом Адриатическом побережье есть n отелей. Каждый отель имеет свою ценность в евро. Sroljo выиграл евро в лотерее. Теперь он хочет купить последовательность последовательных отелей, так что сумма значений этих последовательных отелей как можно больше - но не выше m. Вы должны рассчитать эту максимально возможную общую стоимость. Ввод. В первой строке есть целые числа n и m (1 ≤ n ≤ 300 000, 1 ≤ m <231). В следующей строке есть n натуральных чисел менее 106, представляющих стоимость отеля в том порядке, в котором они лежат вдоль побережья.

Вывод. Распечатайте требуемое число (оно будет больше 0 во всех тестовых данных). Пример ввода 5 1 2 1 3 4 5 Образец вывода 12

Я решил сделать решение этой задачи через метод скользящих окон. Вот мой код

var A = [2, 1, 3, 4, 5]; 
var B = []; 
var n = 5 
var m = 12 
big = -1; 
for (i = 0; i < n; i++) { 
    sum=0; 
    for (j = i; j < n; j++) { 
        sum += A[j]; 
        if (sum < m) { B[i] = sum; continue; } 
        if (sum > m) { B[i] = (sum - A[j]); break; } 
        if (sum == m) { 
            break; 
        } 
    } 
    if (B[i] > big) 
        big = B[i]; 
} 
alert(big);

Похоже мой я не до конца понял как реализовать этот алгоритм, потому что мой код выводит 10, а не 12. Пожалуйста подскажите, укажите на мои ошибки.

Answer 1

финальное значение sum не записывается в массив B

var A = [2, 1, 3, 4, 5];
    var B = [];
    var n = 5
    var m = 12
    big = -1;
    for (i = 0; i <= n; i++) {
        sum=0;
        for (j = i; j <= n; j++) {
            sum += A[j];
            if (sum < m) { B[i] = sum; continue; }//B[i] становится равным сумме
            if (sum > m) { B[i] = (sum - A[j]); break; }
            if (sum == m) {
              B[i] = sum //B[i] становится равным сумме 
                break;
            }
        }
        if (B[i] > big)
            big = B[i];
    }
    alert(big);