排序貪心

區間貪心

刪數貪心

統計二進制下有多少1

int Getbit_1(int n){int cnt=0;while(n){n=n&(n-1);cnt++;}return cnt;
}

暴力加一維前綴和優化

#include <iostream>
#include <climits>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N],sum[N];signed main(){int n,mx=INT_MIN;cin>>n;//先求前綴和for(int i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]+a[i];}for(int l=1;l<=n;l++){for(int r=l;r<=n;r++){// l r 就是區間-->前綴和int sum_l_r=sum[r]-sum[l-1];mx=max(mx,sum_l_r);}}cout<<mx<<endl;return 0;
}

貪心 sum<零 清零

#include <iostream>
#include <climits>
using namespace std;
#define int long long
const int N=2e5+10;signed main(){int n,mx=INT_MIN,sum=0;cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;if(sum<0) sum=0;sum+=x;mx=max(mx,sum);}cout<<mx<<endl;return 0;
}

#include <iostream>
#include <climits>
using namespace std;
#define int long long
const int N=1e2+10;
int a[N][N];
signed main(){int n;cin>>n;//固定左上角 枚舉右下腳for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}}//枚舉int mx=INT_MIN;for(int i1=1;i1<=n;i1++){for(int j1=1;j1<=n;j1++){for(int i2=i1;i2<=n;i2++){for(int j2=j1;j2<=n;j2++){//i1 j1 i2 j2int sum=0;for(int i=i1;i<=i2;i++){for(int j=j1;j<=j2;j++){sum+=a[i][j];}}mx=max(mx,sum);}}}}cout<<mx<<endl;return 0;
}

?

一維前綴和 求二位區間和

#include <iostream>
#include <climits>
using namespace std;
#define int long long
const int N=1e2+10;
int a[N][N],presum[N][N];
signed main(){int n;cin>>n;//固定左上角 枚舉右下腳for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];presum[i][j]=presum[i][j-1]+a[i][j];}}/** 1 2 3 4 5* 6 7 8 9 1* 2 3 2 4 1* 3 3 2 1 1* *///枚舉int mx=INT_MIN;for(int i1=1;i1<=n;i1++){for(int j1=1;j1<=n;j1++){for(int i2=i1;i2<=n;i2++){for(int j2=j1;j2<=n;j2++){int sum=0;for(int i=i1;i<=i2;i++){sum+=presum[i][j2]-presum[i][j1-1];}mx=max(mx,sum);}}}}cout<<mx<<endl;return 0;
}

二維前綴和求區間和

#include <iostream>
#include <climits>
using namespace std;
#define int long long
const int N=1e2+10;
int a[N][N],presum[N][N];
/** 遇到一維數組求最大連續子數組和 以及二維數組求最大連續子數字和問題* 都可以通過暴力枚舉區間來找到最大值* 一、一維數組* 1.對于一維數組，暴力枚舉區間需要兩層循環，l r* 2.求l r 區間內的和可以預先輸入的時候存儲區間和，然后通過區間和求前綴和* 二、二位數組* 1.對于二位數組來說，暴力枚舉區間需要四層循環，就是左上角左邊(i1,j1)，右下角坐標(i2,j2)* 2.對(i1,j1) (i2,j2)求區間和比較復雜，還是輸入的時候前綴區間和，* 3.二維區間和：sum=presum[i2][j2]-presum[i1-1][j2]-presum[i2][j1-1]+presum[i1-1][j1-1]* 4.二維求前綴和的時候，需要畫圖，presum[i][j]=presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]+a[i][j];* */
signed main(){int n;cin>>n;//固定左上角 枚舉右下腳for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];presum[i][j]=presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]+a[i][j];}}/** 1 2 3 4 5* 6 7 8 9 1* 2 3 2 4 1* 3 3 2 1 1* *///枚舉int mx=INT_MIN;for(int i1=1;i1<=n;i1++){for(int j1=1;j1<=n;j1++){for(int i2=i1;i2<=n;i2++){for(int j2=j1;j2<=n;j2++){int sum=presum[i2][j2]-presum[i1-1][j2]-presum[i2][j1-1]+presum[i1-1][j1-1];mx=max(mx,sum);}}}}cout<<mx<<endl;return 0;
}