AcWing 1016. 最大上升子序列和
原题链接
简单
作者:
Zh1995
,
2019-09-22 15:08:17
,
所有人可见
,
阅读 726
import java.util.*;
public class Main{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int len=sc.nextInt();
int nums[]=new int[len+10];
for(int i=1;i<=len;i++)
nums[i]=sc.nextInt();
int f[]=new int[len+10];//以i结尾的子序列和的最大值
//数的取值范围都是非负数、可能重复
for(int i=1;i<=len;i++)
for(int j=0;j<i;j++)
if(nums[i]>nums[j])
f[i]=Math.max(f[i],f[j]+nums[i]);
int res=0;
for(int i=1;i<=len;i++)
res=Math.max(res,f[i]);
System.out.print(res);
}
}