【动态规划】计蒜客：蒜头君闯关（最长递增子序列的变体）

题意： 求递增子序列之和的最大值

dp[i]：以nums[i]结尾的递增子序列之和的最大值

初始化： dp[0]=nums[0]

状态转移方程： dp[i]=max{dp[j]}+num[i] if（nums[j]<nums[i]） 0<=j<i

#include<iostream>using namespace std;int main(){int n;cin>>n;int nums[100];for(int i=0;i<n;i++){cin>>nums[i];}int dp[100];for(int i=0;i<n;i++)dp[i]=nums[i];int res=0;for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(nums[j]<nums[i])dp[i]=max(dp[i],dp[j]+nums[i]);res=max(res,dp[i]);}}cout<<res;}