Max sum

---

问题1

单调队列（贪心法）

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff; 
int main(){
  int t; cin >> t;                 //测试用例个数
  for(int i = 1; i <= t; i++){ 
    int n; cin >> n;              //序列大小
    int maxsum = -INF;            //最大子序和，初始化为一个极小负数
    int start=1, end=1, p=1; //起点，终点，扫描位置
    int sum = 0;                  //子序和
    for(int j = 1; j <= n; j++){
      int a; cin >> a; sum += a;  //读入一个元素，累加 
      if(sum > maxsum){ maxsum = sum; start = p; end = j;}
      if(sum < 0){                //扫到j时，若前面的最大子序和是负数，从下一个重新开始求和 
        sum = 0; 
        p = j+1;
      }
    }
    printf("Case %d:\n",i); printf("%d %d %d\n", maxsum,start,end);
    if(i != t) cout << endl;
  }
  return 0;
}

笔记：贪心算法之所以叫贪心是因为它是局部最优解，最后将所有的解都串联起来的结果就是最终解，本题的要求最大的子序和，子序和是连续的，在遍历序列累加元素时，如果子序和是负数，就清空重新计算子序和

动态规划DP

#include<bits/stdc++.h>
using namespace std;
int dp[100005];                              //dp[i]: 以第i个数为结尾的最大值
int main(){
  int t; cin>>t;
  for(int k=1;k<=t;k++){
    int n; cin >> n;
    for(int i=1;i<=n;i++) cin >> dp[i];     //就用dp[]存储数据a[]
    int start=1, end=1, p=1;                //起点，终点，扫描位置
    int maxsum = dp[1]; 
    for(int i=2; i<=n; i++){
      if(dp[i-1]+dp[i] >= dp[i])            //转移方程dp[i]=max(dp[i-1]+a[i], a[i]);
        {dp[i] = dp[i-1]+dp[i];}            // dp[i-1]+a[i]比a[i]大
      else p = i; // a[i] 更大，那么dp[i]就是a[i]
      if(dp[i]> maxsum ) {                  //dp[i]是一个更大的子序和
        maxsum = dp[i]; start = p; end = i; //以p为开始, 以i为结尾
      }
    }
    printf("Case %d:\n",k); printf("%d %d %d\n", maxsum,start,end);
    if(k != t) cout << endl;
  }
}

笔记：动态规划就是去掉重复运算，每次运算的结果都在“备忘录”里保留，dp[]就是每次运算结果的“备忘录”，qd[]保留了每次子序和的计算结果，a[]添加结束后取dp[]的最大值

问题2

动态规划DP

#include<bits/stdc++.h>
using namespace std;
deque<int> dq;
int s[100005];
int main(){
  int n,m; scanf("%d%d",&n,&m);                //序列长度，窗口大小 
  for(int i=1;i<=n;i++) scanf("%lld",&s[i]);   //储存数据 
  for(int i=1;i<=n;i++) s[i]=s[i]+s[i-1];      //计算前缀和
  int ans = -1e8;：
  dq.push_back(0);
  for(int i=1;i<=n;i++) {
    while(!dq.empty() && dq.front()<i-m) dq.pop_front(); //队头超过m范围：删头 
    if(dq.empty()) ans = max(ans,s[i]);   //如果容器空，历史最大子序和和当前子序和比较
    //[ a[k], ..., a[i] ]  i-k=m
    else ans = max(ans,s[i]-s[dq.front()]); //队头就是最小的s[k]：窗口左端，s[i]-s[k]=窗口
    while(!dq.empty() && s[dq.back()]>=s[i]) dq.pop_back(); //队尾大于s[i]，去尾；大于入队的元素都删除 
    dq.push_back(i);
  }
  printf("%d\n",ans);
  return 0;
}

笔记：问题2在问题1的基础上添加了滑动窗口，处理窗口滑动的最好方式是用队列删头去尾排列元素，队列s[]是前缀和，用差分方式处理窗口内的最大值比较