最大子数组和问题c++
时间: 2023-10-18 17:05:17 浏览: 44
以下是使用动态规划解决最大子数组和问题的C程序:
```
#include <stdio.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int maxSubArraySum(int arr[], int n) {
int max_so_far = arr[0];
int curr_max = arr[0];
for (int i = 1; i < n; i++) {
curr_max = max(arr[i], curr_max + arr[i]);
max_so_far = max(max_so_far, curr_max);
}
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
```
在这个程序中,`maxSubArraySum`函数使用了动态规划方法来计算最大子数组和。使用两个变量`max_so_far`和`curr_max`来跟踪最大子数组和和当前子数组和。在每次迭代中,更新`curr_max`,如果它比原来的更大,则更新`max_so_far`。最后,返回`max_so_far`作为最大子数组和。