public static int MaxSoFar_Lin(int[] arr)
{
    int maxsofar      = 0;
    int maxendinghere = 0;
 
    for (int i = 0; i < arr.Length; i++)
    {
        /* инвариант: значения maxendinghere и
           maxsofar точны для x[0..i-1] */
        maxendinghere = Math.Max(maxendinghere + arr[i], 0);
        maxsofar      = Math.Max(maxendinghere, maxsofar);
    }
    return maxsofar;
}