本文概述
编写一个有效的程序, 以在具有最大和的一维数字数组中找到连续子数组的和。
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
请参考完整的文章最大总和连续子数组更多细节!