最大子段和c++代码_c++局部变量和全局变量存放在哪里

给定由n个整数（可能为负整数）组成的序列a[1],a[2],a[3],…,a[n],最大子段和问题（sum of largest sub-segment problem）要求该序列如a[i]+a[i+1]+…+a[j]的最大值，当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为：Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n。例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-20,11,-4,13,-5,-2)时，最大子段和为20。
在本文中，将介绍两种方法（蛮力法、动态规划法）并分别分析两种方法的时间效率。

蛮力法

蛮力法解决本问题非常简单粗暴，直接用循环嵌套，比较所有子段和的大小，最后输出最大子段和。

代码如下：

#include<iostream> using namespace std; int MaxSubsegmentSum1(int n,int array[]) { 
    int Max=0; for(int i=0;i<n;i++) //起始位置  { 
    for(int j=i;j<n;j++) //结束位置  { 
    int sum=0; for(int k=i;k<=j;k++) //求从i到j的子段和  { 
    sum=sum+array[k]; } if(sum>Max) { 
    Max=sum; } } } return Max; } int main() { 
    int n; cout<<"请输入该序列有多少个数字："; cin>>n; int array[n]; cout<<"请依次输入数字："<<endl; for(int i=0;i<n;i++) { 
    cin>>array