快手[编程题]善变的同伴
链接：https://www.nowcoder.com/questionTerminal/824af5cb05794606b56657bb3fa91f49 来源：牛客网
又到了吃午饭的时间，你和你的同伴刚刚研发出了最新的GSS-483型自动打饭机器人，现在你们正在对机器人进行功能测试。
为了简化问题，我们假设午饭一共有N个菜，对于第i个菜，你和你的同伴对其定义了一个好吃程度（或难吃程度，如果是负数的话……）A[i]，
由于一些技（经）术（费）限制，机器人一次只能接受一个指令：两个数L, R——表示机器人将会去打第L~R一共R-L+1个菜。
本着不浪费的原则，你们决定机器人打上来的菜，含着泪也要都吃完，于是你们希望机器人打的菜的好吃程度之和最大
然而，你善变的同伴希望对机器人进行多次测试（实际上可能是为了多吃到好吃的菜），他想知道机器人打M次菜能达到的最大的好吃程度之和
当然，打过一次的菜是不能再打的，而且你也可以对机器人输入-1, -1，表示一个菜也不打
输入描述:
第一行：N, M
第二行：A[1], A[2], ..., A[N]输出描述:
一个数字S，表示M次打菜的最大好吃程度之和示例1
输入
7 2
1 2 3 -2 3 -10 3输出
10说明
[1 2 3 -2 3] -10 [3]示例2
输入
7 4
1 2 3 -2 3 -10 3输出
12说明
[1 2 3] -2 [3] -10 [3]
第四次给机器人-1, -1的指令备注:
N <= 10^5 = 100000
|A[i]| <= 10^4 = 10000
10%数据M = 1
50%数据M <= 2
80%数据M <= 100
100%数据M <= 10^4 = 10000代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[][] dp = new int[2][n+1];//只保存上一行和当前行
int[] sc = new int[n];
for(int i=0;i<n;i++){
sc[i]=in.nextInt();
dp[0][i]=0;
dp[1][i]=0;
}
int rs=0;
if(m>=n){
for(int i=0;i<n;i++){
if(sc[i]>0){
rs+=sc[i];
}
}
System.out.println(rs);
}else{
for(int i=1;i<=m;i++){
int pre = dp[i & 1][i - 1] = -999999999;
for(int j=i;j<=(i+n-m);j++){
pre=Math.max(pre,dp[(i-1)&1][j-1]);
dp[i & 1][j]= Math.max(pre,dp[i&1][j-1])+sc[j-1];
}
}
rs =-999999999;
int index=m&1;
for(int i=m;i<=n;i++){
rs=Math.max(rs,dp[index][i]);
}
System.out.println(rs);
}
in.close();
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年11月11日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录