Помогите с решением задачи с собеседования.
Тупил полчаса, время вышло, но так и не смог придумать подходящий алгоритм.
Предположительно здесь нужны знания из дискретной математики, возможно, что-то связанное с комбинаторикой.
Я пытался составить массив из последовательностей единиц, и затем для каждой последовательности перебирать всевозможные цепочки с заменой нулей.
Но это ушло в кучу кода, квадратичную сложность и совершенно очевидно не было тем решением, на которое отводилось несколько минут.
Принимаются любые идеи.

// Максимальное количество последовательных единиц

// Дан массив nums содержащий только 0 (нули) и 1 (единицы),
// и целое число k. Верните максимальное количество последовательных
// единиц в массиве, если вы можете заменить не более k нулей на единицы.

// Пример 1:
// nums = [1,1,1,0,0, 0, 1,1,1,1, 0], k = 2
// Ответ: 6
// Замена: [1,1,1,0,0,<1>,1,1,1,1,<1>]
// ---------------
// Выделенные скобками (< >) числа были заменены с 0 на 1.
// Самый длинный подмассив подчеркнут.

// Пример 2:
// nums = [0,0,1,1 ,0, 0, 1,1,1, 0, 1,1,0,0,0,1,1,1,1], k = 3
// nums = [0,1,1,1 ,1, 1, 1,1,1, 0, 1,1,0,0,0,1,1,1,1]
// Ответ: 10
// Объяснение: [0,0,1,1,<1>,<1>,1,1,1,<1>,1,1,0,0,0,1,1,1,1]
// -------------------------
// Выделенные скобками (< >) числа были заменены с 0 на 1.
// Самый длинный подмассив подчеркнут.

// Ограничения:
// 1 <= nums.length <= 105
// nums[i] = 0 или 1.
// 0 <= k <= nums.length

Мой код (не завершен и не работает):

#include <stdio.h>

#define MAX_NUMBER_COUNT 105

int get_max_one_sequences(int nums[], int length, int k) {
    int i, start_index, current_count, max_count;
    if (!nums || length <= 0 || k < 0 || k >= length) return 0;
    if (length > MAX_NUMBER_COUNT) return 0;
    max_count = 0;
    current_count = -1;
    start_index = -1;
    for (i = 0; i < length; i++) {
        if (nums[i] == 1) {
            if (current_count < 0) { start_index = i; }
            current_count++;
        } else {
            if (max_count < current_count) { max_count = current_count; }
            current_count = -1;
        }
    }
    return max_count;
}

void print_array(int nums[], int length) {
    int i;
    if (!nums || length <= 0) return;
    for (i = 0; i < length; i++) {
        printf(i > 0 ? ", %d" : "%d", nums[i]);
    }
    putchar('\n');
}

#define ANSWER 6

int nums[] = { 1,1,1,0,0, 0, 1,1,1,1, 0 };

/**********************************************************************
1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0
k = 2
Result: 3 (must be: 6)
**********************************************************************/
int main(int argc, char *argv[]) {
    int length, k;
    k = 2;
    length = sizeof(nums) / sizeof(nums[0]);
    print_array(nums, length);
    printf("k = %d\n", k);
    printf("Result: %d (must be: %d)\n",
        get_max_one_sequences(nums, length, k), ANSWER);
    return 0;
}