Изображение по сравнению с Растровым классом

Это требует O(n^3) времени из-за того факта, что в трех циклах увеличиваются три различные переменные . То есть, когда один внутренний цикл закончен, это не влияет на внешний цикл. Внешний цикл выполняется столько раз, сколько он должен был работать до того, как был введен внутренний цикл.

И это проблема максимальной смежной суммы подмассивов. Самоочевиден, когда вы видите пример:

{99, 1} => returns 100
{-1, -2, -3} => return -1
{-1, 5, -2} => returns 5
{99, -3, 0, 1} => returns 99

Существует отличный алгоритм, известный как алгоритм Кадане (сделайте это для Google), который решает это за O(n) время.

Вот так:

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

Ссылки: 1 , 2 , 3 .