[leetcode]1749. 任意子数组和的绝对值的最大值(dp)

题目链接

题意

给定一个数组
求任意一个子数组和的绝对值的最大值（子数组可以为空）

方法一

对于最大子段和、最小子段和分别动态规划
最后对abs取max

思路

dpmx[i]表示以nums[i]结尾的子段中最大子段和
dpmn[i]表示以nums[i]结尾的子段中最小子段和

Code

#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=2e5+10,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;
int a[N];class Solution {
public:int maxAbsoluteSum(vector<int>& nums) {int n=nums.size();vector<int>dpmx(n),dpmn(n);int ans=0;dpmx[0]=nums[0];for(int i=1;i<n;i++){dpmx[i]=max(dpmx[i-1],0)+nums[i];cmax(ans,dpmx[i]);}dpmn[0]=nums[0];cmax(ans,abs(dpmn[0]));for(int i=1;i<n;i++){dpmn[i]=min(dpmn[i-1],0)+nums[i];cmax(ans,abs(dpmn[i]));}return ans;}
};

实现细节

注意记得ans要跟dpmn的第一个元素取max

空间优化版

#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=2e5+10,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;
int a[N];class Solution {
public:int maxAbsoluteSum(vector<int>& nums) {int n=nums.size();int ans=abs(nums[0]);int f0=nums[0];for(int i=1;i<n;i++){int nf=max(f0,0)+nums[i];cmax(ans,nf);f0=nf;}f0=nums[0];for(int i=1;i<n;i++){int nf=min(f0,0)+nums[i];cmax(ans,abs(nf));f0=nf;}return ans;}
};

方法二

前缀和 遍历尝试以[1,n-1]每个元素作为子数组结尾的情况 对n个sum取max

思路

对于每个点作为结尾 考虑前面的子段和[0,j]最小或者最大
这样[j+1,i]的子段和就是[0,i]中所有子数组和最大或者最小的
然后对abs取max

---

这里使用set维护前面的子段和 也可以开一个大根堆和一个小根堆

Code

class Solution {
public:int maxAbsoluteSum(vector<int>& nums) {int n=nums.size();set<int>st;int sum=0,ans=0;st.emplace(0);for(int i=0;i<n;i++){sum+=nums[i];ans=max({ans,abs(sum-*st.begin()),abs(sum-*st.rbegin())});st.emplace(sum);}return ans;}
};