非常经典的dp问题

题目

• 如何理解 当前子序碰到 a[i]<0 加不加到子序中
• 如果将a[i]加入到sum中，sum仍然>0,那么加入是有意义的，否则没有意义，即是加入a[i] a[i]<0使得sum减小，但我们已经记录上一个sum作为最大的自序和，并且加入a[i]后，a[i+1]更大，成为新的最大子序和。
• 因为求最大子序的和，当 $sum[i-1]+a[i]<=a[i]$ 加入到自序和中，是没有任何意义的，说明$sum[i]<=0$,那么开始记录新的子序和 $sum[i]=a[i]$
• dp[i]=max(a[i],dp[i-1]+a[i])即是$dp[i-1]+a[i]>=a[i]$ 第i步才开始判断i-1步的sum的和是否为<0，

  class Solution {
  public:
      int maxSubArray(vector<int>& nums) {
          int len=nums.size();
          if( len == 0) return 0;
          vector<int> dp(len);
          dp[0]=nums[0];
          for(int i=1;i<len;i++) dp[i]=max(dp[i-1]+nums[i],nums[i]);
          return *max_element(dp.begin(),dp.end());
      }
  };

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len=nums.size();
        if( len == 0) return 0;
        int ans=nums[0],sum=nums[0];
        for(int i=1;i<len;i++){
            if( sum>0 ) sum+=nums[i];//先判断sum的值是否>0
            else sum=nums[i];
            
            if(sum>ans) ans=sum;
        }
        return ans;
    }
};

子段的长度<=m

加上了长度限制 自区间的和一定想到用前缀和来算

• 用单调队列，维护sum值非递减的队列，存索引，

• 先判断长度，然后更新ans,最后把当前sum[i]在满足性质的条件下入队

  #include <iostream>
  using namespace std;
  const int maxn=300005;
  long long sum[maxn];
  int q[maxn];
  int main() {
      freopen("a.txt","r",stdin);
      int     n,m;
      scanf("%d%d",&n,&m);
      for (int i=1;i<=n;i++) {
          int  t;
          scanf("%d",&t);
          sum[i] += sum[i-1] + t ;
      }
      long long ans = 0;
      int l=1,r=1;//队列区间从1开始
      q[1]=0; //队列最开始的sum和最小的为0,维护单调递增的性质,存sum的下标
      for (int i=1;i<=n;i++) {
          while ( l<=r && q[l] < i-m ) l++;
          ans = max( ans,sum[i] - sum[q[l]] );//q[l]是满足长度时，sum最小的值
          //将sum[i]加入到队列中
          while ( l<=r && sum[i] <= sum[q[r]] ) r--;
          q[++r] = i;
      }
      printf("%lld",ans);
      return 0;
  }

  子段的长度不小L

• 长度最小为L，那么不难想到 ，在sum数组中固定i,则要使得子序列和最大，从[0,i-L]中找出sum最小的，则ans最大

• 公式：
  $ans=max_{L<=i<=n}( sum_i - min(sum_{0<=j<=i-L}j) )$

• 用一个min_val变量记录min{sum[j]} (0<=j<=i-L)

  double ans = 1e-10;
  double min_val = 1e10;
  for (int i = L; i <= n; i++) {
      min_val = min( min_val , sum[i-L] );//j=i-L
      ans = max( ans,sum[i]-min_val );
  }