求数列的最大子段和 给定n个元素的整数列(可能有负整数)a1,a2,···,an,求形如: ai,ai+1,···,aj i,j=1,2,···,n, i<=j 的子段和,使其为最大。当所有整数均为负整数时定义其最大字段和为0。 如(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)时最大子段和为:a2+a3+a4=20
时间: 2023-08-22 11:03:33 浏览: 40
以下是求解最大子段和的C语言代码,使用了Kadane算法:
```c
#include <stdio.h>
#include <limits.h>
int maxSubArraySum(int arr[], int n)
{
int max_so_far = INT_MIN, max_ending_here = 0;
int i;
for (i = 0; i < n; i++)
{
max_ending_here = max_ending_here + arr[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;
}
int main()
{
int arr[] = {-2, 11, -4, 13, -5, -2};
int n = sizeof(arr) / sizeof(arr[0]);
int max_sum = maxSubArraySum(arr, n);
printf("Maximum contiguous sum is %d", max_sum);
return 0;
}
```
其中,`arr`数组表示给定的整数列,`n`表示元素个数。函数`maxSubArraySum`返回最大子段和。