Жадное решение за 120*(n+30) итераций:
1) Пробегаем по массиву окном в 30 кадров, находим максимальную сумму, запоминаем (кладём в массив результата).
2) Полученным 30 кадрам присваиваем отрицательный вес (например, равный -30 * (макс.значение в массиве), дабы точно не попал в следующую выборку).
3) Повторяем п 1-2 120 раз, пока не получим 120 не пересекающихся диапазонов (если отрицательное значение в пункте 2 выбрано правильно), отсортированных по убыванию веса. Естественно, если мы храним их как пару (время, вес), то можем потом обратно отсортировать по времени.