窮舉法：
int MaxSubArraySum(int a[], int n)
{
int i, j, MaxSum = 0, tmpSum, cnt;
?
for (i=1; i<=n; i++)
{
for (j=0; j+i<=n; j++)
{
cnt = 0;
tmpSum = 0;
while (cnt < i)
{
tmpSum += a[j+cnt];
cnt++;
}
if (MaxSum < tmpSum)
{
MaxSum = tmpSum;
}
}
}
?
return MaxSum;
}
?
通過循環嵌套，控制步長，求出所有的子數組的值
?
找出規律法：
int MaxSub(int a[], int n)
{
int sum = 0, tmpSum = 0;
int i;
?
for (i=0; i<n; i++)
{
if (tmpSum <= 0)
{
tmpSum = a[i];
}
else
{
tmpSum += a[i];
}
if (sum < tmpSum)
{
sum = tmpSum;
}
}
?
return sum;
}
?
這個代碼就簡潔了很多，時間復雜度也達到了題目要求的O(n)
寫出這種算法的關鍵在于，弄清楚當子數組的和小于0時就可以舍棄掉，從下一個元素開始計算子數組和了。
)
猜想)
