首页编写程序找出序列的最大子段和 C++代码

编写程序找出序列的最大子段和 C++代码

时间: 2024-05-10 14:20:00 浏览: 112

以下是一个简单的 C 代码实现，使用 Kadane 算法： ``` #include <stdio.h> int maxSubArraySum(int a[], int size) { int max_so_far = a[0]; int curr_max = a[0]; for (int i = 1; i < size; i++) { curr_max = (a[i] > curr_max + a[i]) ? a[i] : curr_max + a[i]; max_so_far = (curr_max > max_so_far) ? curr_max : max_so_far; } return max_so_far; } int main() { int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}; int n = sizeof(arr)/sizeof(arr[0]); int max_sum = maxSubArraySum(arr, n); printf("Maximum contiguous sum is %d\n", max_sum); return 0; } ``` 该程序使用一个循环遍历数组并更新最大子段和和当前子段和。如果当前元素比当前子段和加上当前元素更大，则更新当前子段和，否则保持不变。在每个迭代中，最大子段和也会相应更新。此程序的输出为： ``` Maximum contiguous sum is 7 ```

阅读全文