2D Algorithm Kadan



  • It was necessary to bring the Kadan algorithm to a two-storey mass. Some of the realities of this algorithm have been found, but they all do not understand and use another approach to find partial amounts. That's why I started writing myself. What am I doing wrong? These input data should be 15

    Looking for the maximum amount. I described the idea.

    https://ideone.com/Ov6040

    #include <iostream>
    #include <vector>
    

    int main(){
    int n, p;
    int sum = 0, max_sum = 0;
    std::vector< std::vector<int> > m;

    std::cin.sync_with_stdio(false);
    std::cin &gt;&gt; n;
    // Устанавливаем размеры матрицы, которая хранит суммы
    m.resize(n);
    for(int i = 0; i &lt; n; i++)
        m[i].resize(n);
    
    // Если индексы указывают на первую ячейку строки, то просто копируем в нее введенное число
    // В противном случае копируем в нее сумму числа из предыдущей ячейки и введенного
    // Таким образом, i-я ячейка строки хранит сумму первых i чисел
    for(int i = 0; i &lt; n; i++)
        for(int j = 0; j &lt; n; j++){
            std::cin &gt;&gt; p;
            if(j) m[i][j] = m[i][j - 1] + p;
            else  m[i][j] = p;
        }
    
    for(int left = 0; left &lt; n; left++) // Фиксируем левый столбец искомой матрицы
        for(int right = left; right &lt; n; right++){  // Двигаем правый столбец искомой матрицы вправо
            sum = 0;
            for(int j = 0; j &lt; n; j++){ // Цикл для суммирования по столбцу
                if(right == 0)
                    sum += m[j][right]; // Суммируем элементы первого столбца
                else
                    sum += m[j][right] - m[j][left - 1];
                if(sum &lt; 0) sum = 0;
                max_sum = std::max(sum, max_sum);
            }
        }
    
    for(int i = 0; i &lt; n; i++){
        for(int j = 0; j &lt; n; j++)
            std::cout &lt;&lt; m[i][j] &lt;&lt; " ";
        std::cout &lt;&lt; std::endl;
    }
    
    std::cout &lt;&lt; max_sum &lt;&lt; std::endl;
    
    std::cin &gt;&gt; p;
    

    FS. Force sum I've been texting a few times, and it's always been wrong.



  • Ideas http://codeforces.com/blog/entry/13713 Simplified and faster:

    for(int i = 0; i < N; i++){
        max_ending_here += Number[i];
            if(max_ending_here > max_so_far)max_so_far = max_ending_here;
            if(max_ending_here < 0)max_ending_here = 0;
    }
    

    PHP programme (indicating sequence):

    $n = array(34, -41, 59, 26, -53, 58, 97, -93, -23, 84);
    

    $start = -1; // начальный индекс
    $finish = -1; // конечный индекс
    $msf = 0; // максимальная сумма для групп с начальным индексом $start
    $meh = 0; // максимальная сумма для групп с конечным индексом $finish

    $len = count($n);
    for ($i=0; $i<$len; $i++){
    if($meh==0) $start=$i;
    $meh = $meh + $n[$i];
    if($meh>$msf){
    $finish = $i;
    $msf = $meh;
    }
    $meh = max($meh,0);
    printf("<br>N[$i] = %d &emsp; msf = $msf &emsp; mex = $meh &emsp; start = $start &emsp; finish = $finish", $n[$i]);
    }
    printf("<br><br>Алгоритм Кадане: сумма N[$start:$finish] = %d", $msf);

    Results:

    N[0] = 34 msf = 34 mex = 34 start = 0 finish = 0
    N[1] = -41 msf = 34 mex = 0 start = 0 finish = 0
    N[2] = 59 msf = 59 mex = 59 start = 2 finish = 2
    N[3] = 26 msf = 85 mex = 85 start = 2 finish = 3
    N[4] = -53 msf = 85 mex = 32 start = 2 finish = 3
    N[5] = 58 msf = 90 mex = 90 start = 2 finish = 5
    N[6] = 97 msf = 187 mex = 187 start = 2 finish = 6
    N[7] = -93 msf = 187 mex = 94 start = 2 finish = 6
    N[8] = -23 msf = 187 mex = 71 start = 2 finish = 6
    N[9] = 84 msf = 187 mex = 155 start = 2 finish = 6

    Kadan: sum N[2:6] = 187

    Table https://docs.google.com/spreadsheets/d/1yxbGiDVE8JoKZgIxOPj_D0RtBuC1phBWZ6R3VpWgauQ/edit#gid=0 😞
    Kadane2

    P.S. The single-dimensional function can also be applied in 2D algorithms. By placing the sums of 1.2.3.4 nearby lines at the entrance, the task is complete.

    2D - The programme is:

    $n = array(
    array( 0, 2,-7, 0),
    array( 9, 2,-6, 2),
    array(-4, 1,-4, 1),
    array(-1, 8, 0, -2),
    );

    function kadane_1d($n) { // на входе 1D массив, на выходе - сумма
    $start = -1; // начальный индекс
    $finish = -1; // конечный индекс
    $msf = 0; // максимальная сумма для групп с начальным индексом $start
    $meh = 0; // максимальная сумма для групп с конечным индексом $finish
    $len = count($n);
    for ($i=0; $i<$len; $i++){
    $meh = $meh + $n[$i];
    if($meh>$msf){
    $msf = $meh;
    }
    $meh = max($meh,0);
    printf(" %d&emsp;", $n[$i]);
    }
    printf("Алгоритм Кадане 1D: сумма N = %d<br>", $msf);
    return $msf;
    }

    $rows = count($n);
    $cols = count($n[0]);
    $sums = array();
    $max = 0;

    for($h=0; $h<$rows; $h++){ // цикл по высоте матриц
    printf("<br>Строк в подматрицах: %d<br>", $h+1);
    for ($i=0; $i<$rows-$h; $i++) {
    if($h==0){
    $sums[$i] = $n[$i];
    }else{
    for($j=0; $j<$cols-1; $j++) // пересчёт сумм
    $sums[$i][$j] += $n[$h+$i][$j];
    }
    $k = kadane_1d($sums[$i]);
    $max = ($k>$max) ? $k : $max;
    }
    }
    print("<br>Максимальная сумма равна: $max")

    Result:

    Line in submarines: 1
    0 2 -7 0 Algorithm Kadan 1D: sum N = 2
    9 2 - 6 2 Algorithm Kadan 1D: sum N = 11
    -4 1 Algorithm Kadan 1D: sum N = 1
    -1 8 0-2 Algorithm Kadan 1D: sum N = 8

    Line in submarines: 2
    9 4 - 13 0 Algorithm Kadan 1D: sum N = 13
    5 3 - 10 2 Algorithm Kadan 1D: sum N = 8
    -5 9 - 4 1 Algorithm Kadan 1D: sum N = 9

    Line in submarines: 3
    5 5 - 17 0 Algorithm Kadan 1D: sum N = 10
    4 11 - 10 2 Algorithm Kadan 1D: sum N = 15

    Line in submarines: 4
    4 13 - 17 0 Algorithm Kadan 1D: sum N = 17

    The maximum amount is 17




Suggested Topics

  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2