3665顺序表应用8：最大子段和之动态规划法
#include<iostream> #include<cstdlib> #define MAX 100010 #define OVERFLOW -1 using namespace std; int cnt ; typedef struct { int *elem; int listlen1; int listsize1; }list; void CreatList(list &l,int n)//list & 主函数带入直接用表名 { l.elem=new int [MAX]; for(int i=0;i<n;i++) cin>>l.elem[i]; } int maxsum(list*l,int n)//list * 主函数带入需要在表名前加地址符& { int max=0,max1=0,i; for(i=0;i<=n-1;i++) { max1+=l->elem[i]; if(max1<0)//使连续负数和为0 max1=0; if(max1>max)//保证输出的值为最大 max=max1; } return max; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); int m,t,k,n,i; cin>>n; list newlist; CreatList(newlist,n); int ss = maxsum(&newlist,n); cout<<ss<<" "<<endl; return 0; }