方法1:暴力法
遍历数组三次(i in 0..len, j in i..len, k in i..j),在第三次(k in i..j)求和sum+=data[k],并与当前max比较,大则更新max值,小max值不变
时间复杂度为O(n^3);
具体代码实现:
int max(int a, int b) { return (a>b ? a : b); }
int max_sub_sum(int *data, int len)
{
int sum=0, maxsofar=0;
int i=0, j=0, k=0;
for(i=0; i<=len; i++)
{
for(j=i; j<=len; j++)
{
sum=0;
for(k=i; k<=j; k++)
{
sum += data[k];
maxsofar = max(maxsofar, sum);
}
}
}
return m......
阅读全文