链接:
https://leetcode.cn/problems/maximum-alternating-subsequence-sum/
题意:
给定一个数组,求一个子序列,使这个子序列的奇数位和-偶数位和最大(下标从1开始的话|反正第一个数是+)
解:
找下坡,曲折处两个分下坡大于一个总下坡(如图)
实际代码:
思维:
#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?:文章来源:https://www.toymoban.com/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;
}
限制:文章来源地址https://www.toymoban.com/news/detail-557345.html
1 <= nums.length <= 105
1 <= nums[i] <= 105
到了这里,关于2023-07-11力扣每日一题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!