Podciąg o największej sumie – Algorytm Kadane Kod

C++

#include <iostream>
using namespace std;

int Kadane(int arr[], int size)
{
   int max_sum = arr[0], max_current = arr[0];
 
   for(int i = 1; i < size; i++)
   {
        max_current = max(arr[i], max_current + arr[i]);
        max_sum = max(max_sum, max_current);
   }
   return max_sum;
}
 
int main()
{
    int arr[] = {3, -3, 2, -1, 4, -6, -9, 4};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout << "Podciąg o największej sumie: " << Kadane(arr, size) << endl; 
    return 0;
}

Java

public class Program
{
    static int Kadane(int arr[])
    {
        int max_sum = arr[0], max_current = arr[0];
        int size = arr.length;
 
        for(int i = 1; i < size; i++)
        {
            max_current = Math.max(arr[i], max_current + arr[i]);
            max_sum = Math.max(max_sum, max_current);
        }
        return max_sum;
    }
 
    public static void main(String[] args)
    {
        int arr[] = {3, -3, 2, -1, 4, -6, -9, 4};
        System.out.println("Podciag o najwiekszej sumie: " + Kadane(arr));
    }
}

Python

def Kadane(arr):
     
    max_sum = max_current = arr[0]
     
    for i in range(1, len(arr)):
        max_current = max(arr[i], max_current + arr[i])
        max_sum = max(max_sum, max_current)
         
    return max_sum
 
arr = [3, -3, 2, -1, 4, -6, -9, 4]
print("Podciąg o największej sumie: " + str(Kadane(arr)))

C#

using System;
 
class Program
{
    static int Kadane(int []arr)
    {
        int max_sum = arr[0], max_current = arr[0], size = arr.Length;
 
        for (int i = 1; i < size; i++)
        {
            max_current = Math.Max(arr[i], max_current + arr[i]);
            max_sum = Math.Max(max_sum, max_current);
        }
        return max_sum;
    }
 
    public static void Main ()
    {
        int []arr = {3, -3, 2, -1, 4, -6, -9, 4};
        Console.Write("Podciag o najwiekszej sumie: " + Kadane(arr));
    }
}

PHP

<?php
function Kadane($arr)
{
    $max_sum = $max_current = $arr[0];
    $size = sizeof($arr);
     
    for ($i = 1; $i < $size; $i++)
    {
        $max_current = max($arr[$i], $max_current + $arr[$i]);
        $max_sum = max($max_sum, $max_current);
    }
    return $max_sum;
}
 
$arr = array(3, -3, 2, -1, 4, -6, -9, 4);
echo "Podciąg o największej sumie: " . Kadane($arr);
?>

Javascript

<script>
 
function Kadane(arr)
{
    let max_sum = max_current = arr[0];
    let size = arr.length;
 
    for (let i = 1; i < size; i++)
    {
        max_current = Math.max(arr[i], max_current + arr[i]);
        max_sum = Math.max(max_sum, max_current);
    }
    return max_sum;
}
 
let arr = [3, -3, 2, -1, 4, -6, -9, 4];
document.write("Podciąg o największej sumie: ", Kadane(arr));
     
</script>

VBA

Function Kadane(Zakres As Range) As Integer
    Dim max_sum As Integer
    Dim max_current As Integer
    max_sum = Cells(1, 1)
    max_current = Cells(1, 1)
    
    For i = 2 To Zakres.Count
        
        max_current = WorksheetFunction.Max(max_current + Cells(i, 1), Cells(i, 1))
        max_sum = WorksheetFunction.Max(max_current, max_sum)
        
    Next i
    Kadane = max_sum
    
End Function