Задача на динамическое программирование по подотрезкам

Есть массив элементов A состоящий из n чисел (n <= 5000). Давайте рассмотрим все возможные наборы из k элементов (k <= n), которые можно составить из чисел этого массива. Наборы считаются различными, если числа хотя бы на одной из k позиций различаются (если числа одинаковые, пусть даже они и представлены элементами массива с разными индексами, наборы считаются одинаковыми).

Теперь возьмём сумму индексов (числа нумеруются с единицы) всех максимумов набора, т.е. для набора (2, 1, 2) эта сумма равна 4 (1 + 3), а для набора (1, 2, 3) эта сумма равна 3 (здесь единственный максимум с индексом 3).

Ваша задача — просуммировать значение этих сумм для всех различных наборов, которые могут быть составлены из заданного массива.

Идей нет, можете чем нибудь-нибудь помочь? Язык решения не так важен, главное идея, которую и псевдокодом можно написать.