用于最大总和连续子数组的C#程序

2021年5月8日16:23:08 发表评论 827 次浏览

本文概述

编写一个有效的程序, 以在具有最大和的一维数字数组中找到连续子数组的和。

卡丹算法

C#

//C# program to print largest
//contiguous array sum
using System;
  
class GFG {
     static int maxSubArraySum( int [] a)
     {
         int size = a.Length;
         int max_so_far = int .MinValue, max_ending_here = 0;
  
         for ( int i = 0; i <size; i++) {
             max_ending_here = max_ending_here + a[i];
  
             if (max_so_far <max_ending_here)
                 max_so_far = max_ending_here;
  
             if (max_ending_here <0)
                 max_ending_here = 0;
         }
  
         return max_so_far;
     }
  
     //Driver code
     public static void Main()
     {
         int [] a = { -2, -3, 4, -1, -2, 1, 5, -3 };
         Console.Write( "Maximum contiguous sum is " + maxSubArraySum(a));
     }
}
  
//This code is contributed by Sam007_

输出如下:

Maximum contiguous sum is 7

如果我们将max_so_far与max_ending_here进行比较, 则仅当max_ending_here大于0时, 才能进一步优化上述程序。

C#

static int maxSubArraySum( int [] a, int size)
{
     int max_so_far = 0, max_ending_here = 0;
  
     for ( int i = 0; i <size; i++) {
         max_ending_here = max_ending_here + a[i];
         if (max_ending_here <0)
             max_ending_here = 0;
  
         /* Do not compare for all
     elements. Compare only 
     when max_ending_here> 0 */
         else if (max_so_far <max_ending_here)
             max_so_far = max_ending_here;
     }
     return max_so_far;
}
  
//This code is contributed
//by ChitraNayal

请参考完整的文章最大总和连续子数组更多细节!

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: