http://acmp.ru/asp/do/index.asp?main=task&id_course=2&id_section=20&id_topic=46&id_problem=289

Пример этой задачи можно было встретить год-два назад на городском этапе лио.
Решение состоит либо в использовании сложных структур, либо в модифицированной сортировке слиянием (merge sort), которая считает сколько элементов слева меньше текущего.

Решение задачи можно реализовать с помощью не сложной структуры - sqrt декомпозиции

Позволяет отвечать на запроса за sqrt(n)

http://e-maxx.ru/algo/sqrt_decomposition

Начало эры ДП

http://acmp.ru/index.asp?main=task&id_task=121

Чуть похитрее ДП

Повторение - мать учения

http://acmp.ru/index.asp?main=task&id_task=500

Чуть-чуть классики в нашей жизни...
Задача: дан массив целых чисел (размер массива < 10^8, конкретно число массива по модулю менее 10^9).
Необходимо найти отрезок массива, с максимально возможной суммой, и вывести эту сумму.

Пример.
1 2 3 4 -10

Максимальная сумма на отрезке [1; 4] = 10

Свои идеи, размышления, пишите в Иго.

Ну или если вам слишком абстрактно такое условие - вот задача

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=649&page=show_problem&problem=448

Motivation from Ingus & Alexander
https://www.youtube.com/watch?v=7qTn4mNeH9o