鏈接：
https://leetcode.cn/problems/maximum-alternating-subsequence-sum/
題意：
給定一個(gè)數(shù)組，求一個(gè)子序列，使這個(gè)子序列的奇數(shù)位和-偶數(shù)位和最大（下標(biāo)從1開始的話|反正第一個(gè)數(shù)是+）
解：
找下坡，曲折處兩個(gè)分下坡大于一個(gè)總下坡（如圖）
實(shí)際代碼：
思維：
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long int ll;
const int Nmax=1E5+7;
long long maxAlternatingSum(vector<int>& nums)
{
ll ans=0;bool zt=1;int temp=nums[0];
for(int i=1;i<nums.size();i++)
{
if(zt && nums[i]<nums[i-1]) zt=0;
if(!zt && nums[i]>nums[i-1])
{
ans+=temp-nums[i-1];
zt=1;temp=nums[i];
}
temp=max(temp,nums[i]);
}
return ans+temp;
}
int main()
{
vector<int> nums;
int n;cin>>n;
for(int f=1;f<=n;f++)
{
int temp;cin>>temp;
nums.push_back(temp);
}
ll ans=maxAlternatingSum(nums);
cout<<ans<<endl;
}
DP?：文章來源：http://www.zghlxwxcb.cn/news/detail-557345.html
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long int ll;
const int Nmax=1E5+7;
long long maxAlternatingSum(vector<int>& nums)
{
ll A1=0,A2=0;//最后一位+ 最后一位-
int lg=nums.size();
for(int i=0;i<lg;i++)
{
A1=max(A2+nums[i],A1);
if(i!=0) A2=max(A1-nums[i],A2);
}
return max(A1,A2);
}
int main()
{
vector<int> nums;
int n;cin>>n;
for(int f=1;f<=n;f++)
{
int temp;cin>>temp;
nums.push_back(temp);
}
ll ans=maxAlternatingSum(nums);
cout<<ans<<endl;
}
限制：文章來源地址http://www.zghlxwxcb.cn/news/detail-557345.html
1 <= nums.length <= 1051 <= nums[i] <= 105
到了這里，關(guān)于2023-07-11力扣每日一題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
