1.自己的思路：前缀和，代码如下：
int main()
{
int a[100010]={0};
int b[100010]={0};
int k;
cin>>k;
for(int i=0;i<k;i++)
{
cin>>a[i];
if(i==0)
b[i]=a[i];
else
b[i]=b[i-1]+a[i];
}
int max=0;
for(int i=0;i<k;i++)
{
for(int j=i;j<k;j++)
{
if(max<b[j]-b[i])
{
max=b[j]-b[i];
}
}
}
cout<<max<<endl;
system("pause");
return 0;
}
缺点：
两层嵌套循环，导致当数据很多的时候会运行超时
2.最优解：
KaDane算法（最大子序列算法），能够最大程度减少时间复杂度，优化程序运行时间，本质上是贪心算法的一种
代码如下：
int main()
{
int a[100010]={0};
int k;
cin>>k;
for(int i=0;i<k;i++)
{
cin>>a[i];
}
int max_sum=a[0]; //全局最大和
int current_sum=a[0]; //当前子数组的和
for(int i=1;i<k;i++)
{
//核心逻辑：当前元素要么加入前一子数组，要么单独作为新子数组的节点
current_sum=(current_sum+a[i]>a[i])? (current_sum+a[i]):a[i];
//更新全局最大和
if(current_sum>max_sum)
max_sum=current_sum;
}
cout<<max_sum<<endl;
system("pause");
return 0;
}
核心逻辑：
1.贪心算法，每次多遍历一个节点时，找到在当前节点的最大和
2.更新全局最大和可以理解为数学函数图像中的记录峰值，记录一个个极大值，不断更新最大值，从而将贪心算法的局部最优解转化为全局最优解