最大子序列和 动态规划
时间: 2023-11-05 14:59:04 浏览: 73
最大子序列和问题是一个经典的动态规划问题。给定一个序列,我们需要找到其中连续子序列的和的最大值。
算法过程如下:
1. 初始化两个变量:max_sum为当前最大子序列和,cur_sum为当前正在计算的子序列和,初始值都为序列中的第一个元素。
2. 从序列的第二个元素开始遍历:
a. 如果cur_sum加上当前元素小于当前元素本身,则将cur_sum更新为当前元素。
b. 如果cur_sum加上当前元素大于等于当前元素本身,则将cur_sum更新为cur_sum加上当前元素。
3. 每次更新cur_sum时,都将cur_sum与max_sum比较,更新max_sum为两者中的较大值。
4. 遍历完整个序列后,max_sum即为最大子序列和。
参考代码如下:
```
int maxSubArraySum(int arr[], int n) {
int max_sum = arr[0];
int cur_sum = arr[0];
for (int i = 1; i < n; i++) {
if (cur_sum + arr[i] < arr[i]) {
cur_sum = arr[i];
} else {
cur_sum = cur_sum + arr[i];
}
if (cur_sum > max_sum) {
max_sum = cur_sum;
}
}
return max_sum;
}
```
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)