最大子序列（C++ 详细注释）

解题思路:这个用的动态规划,从第一个数遍历到最后一个数，时间复杂度就是O（n）
这个题重点就是要求是最大子序列，那么从前往后的子序列中出现子序列为小于等于0

就说明这个子序列是没意义不能要的

因为加上这个子序列就不满足最大的子序列了

明白这个相信这个题也就迎刃而解了

注意事项:

参考代码:

#include

using namespace std;

//求最大子段和算法 

int MaxSum(int* a, int n) {

int sum = 0, b = 0;

for (int i = 1; i <= n; i++) {

if (b > 0) {

b += a[i];//如果大于0，就说明可以加

}

else {//如果b<=0,就说明之前放的子序列都没意义，因为要求子段和最大

b = a[i];

}

if (b > sum) {//更新最大值

sum = b;

}

}

return sum;

}

int main() {

int a[100], n;

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> a[i];

}

cout  << MaxSum(a, n) << endl;

return 0;

}