题目
如果我们有这样一个数组sum，sum[i]表示第1个到第i个数的和。快速计算第i个到第j个这个序列的和只要用sum[j] - sum[i-1]就可以了！这样的话，我们就可以省掉最内层的循环，让我们的程序效率更高！时间复杂度比传统的暴力更优，O（n2）
int main()
{
int k;
cin >> k;
//int *p = new int[k];
vector<int> a(k);
vector<int> sum(k+1,0);
for (int i = 0; i < k; i++)
cin >> a[i];
for (int i = 1; i <= k; i++)//sum[0]=0,方便计算
sum[i] = a[i-1] + sum[i - 1];
int max = sum[0];
for(int i = 1; i <= k; i++)
for (int j = i; j <= k; j++)
{
int temp = sum[j] - sum[i-1];
if (temp > max)
max = temp;
}
cout << max << endl;
//delete[] p;
system("pause");
return 0;
}
第二种是利用分治的思想，将问题划分成左中右，然找出左边，右边，跨中间最大的。时间复杂度O（nlogn）
int solve(int left,int right,vector<int> &a)
{
//序列长度为1时
if (left == right)
return a[left];
//划分成两个更小的子问题
int mid = (left + right) / 2;
int lmax = solve(left, mid, a);
int rmax = solve(mid + 1, right, a);
//在中间的情况
int sum = 0, lm = 0, rm = 0;
for (int i = mid; i >= left; i--)
{
sum += a[i];
if (lm < sum)
lm = sum;
}
sum = 0;
for (int i = mid+1; i <= right; i++)
{
sum += a[i];
if (rm < sum)
rm = sum;
}
//去三个当中最大的
int max = rm + lm;
if (lmax > max)
max = lmax;
if (rmax > max)
max = rmax;
return max;
}
int main()
{
int k;
cin >> k;
//int *p = new int[k];
vector<int> a(k);
for (int i = 0; i < k; i++)
cin >> a[i];
int max = solve(0,k-1,a);
cout << max << endl;
system("pause");
return 0;
}
递归的思想，我们用dp[n]表示以第n个数结尾的最大连续子序列的和，于是存在以下递推公式：dp[n] = max(0, dp[n-1]) + num[n]，然后取dp[n]中最大的，在代码中直接用原数组保存了dp。时间复杂度O（n）
max(dp[m]) | m∈[1, N]。
int main()
{
int k;
cin >> k;
//int *p = new int[k];
vector<int> a(k);
for (int i = 0; i < k; i++)
cin >> a[i];
int max = 0;
if (k == 1)
{
if (a[0] < 0)
max = 0;
}
else
{
for (int i = 1; i < k; i++)
{
if (a[i - 1] > 0)
a[i] = a[i] + a[i - 1];
if (a[i] > max)
max = a[i];
}
}
cout << max << endl;
system("pause");
return 0;
}
边输入边判断，计算sum，如果和大就保存下来，这是这一块的最大值。如果小于零说明这个不合适，加上的话会让前边的值减小，前边的已经到了最大，接着重新计算下一段最大的sum。
int main()
{
int k;
cin >> k;
//int *p = new int[k];
vector<int> a(k);
for (int i = 0; i < k; i++)
cin >> a[i];
int sum = 0;
int max = 0;
for (int i = 0; i < k; i++)
{
sum += a[i];
if (sum > max)
max = sum;
else if (sum < 0)
sum = 0;
}
//也可以不用vector，直接输入一个就判断，减小空间复杂度。
cout << max << endl;
system("pause");
return 0;
}
也可以不用vector，直接输入一个就判断，减小空间复杂度。
int main()
{
int k;
cin >> k;
int a;
int sum = 0;
int max = 0;
for (int i = 0; i < k; i++)
{
cin >> a;
sum += a;
if (sum > max)
max = sum;
else if (sum < 0)
sum = 0;
}
//也可以不用vector，直接输入一个就判断，减小空间复杂度。
cout << max << endl;
system("pause");
return 0;
}
