前缀和是指某序列的前n项和,可以把它理解为数学上的数列的前n项和,而差分可以看成前缀和的逆运算。合理的使用前缀和与差分,可以将某些复杂的问题简单化。
输入一个长度为n的整数序列。接下来再输入m个询问,每个询问输入一对l, r。对于每个询问,输出原序列中从第l个数到第r个数的和。
用暴力的方式 很容易实现,时间复杂度是O(n*m)。
但是如果我们进行预处理
const int N=1e7+5; int sum[N],a[N]; for (int i=1;i<=n;i++) { sum[i]=sum[i-1]+a[i];//即 sum[i]表示a[1]~a[i]的和 }
根据高中的数列知识很容易知道 a[i]=sum[i]-sum[i-1];
cout<<sum[i]-sum[i-1];//查询i开始到i结束的值 l~r 即可表示为: (sum[r]-sum[r-1])+(sum[r-1]-sum[r-1-1])+...+sum[l]-sum[l-1]; 化简成 sum[r]-sum[l-1]; 输出原序列中从第l个数到第r个数的和。 cout<<sum[r]-sum[l-1];
即可解决,这样每次查询只用 输出结果即可,查询复杂度为O(1),这也是一维前缀和。
首先我们会考虑和之前一样的进行预处理 然后用两个for 遍历所有的查询,每次保留最大的。时间复杂度O(n*n)
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int sum[N], a[N]; int n; int ans = -0x3f; int main () { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; sum[i] = sum[i - 1] + a[i]; } for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) //考虑到是求最长字段和 我认为 一个也算字段 { ans = max(ans, sum[j] - sum[i - 1]); //想到特判 i==0的时候,sum[1]-sum[0],全局变量sum[0]==0 } } cout << ans; }
提交
TLE