善变的同伴

//优化了一下通过答案中“流淌201711202027933”的解法，主要是给二维dp直接赋初值，这样可以减少一个循环
//同时增加了一些注释，提高可读性
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>ss;
int dp[2][100005]={0};
int main()
{
    int N, M,sum,h,  k, count, now; //N表示菜的个数，M表示机器人最多打菜的次数，cout表示菜的总的好吃度，now表示当前这道菜的好吃度
    cin >> N >> M;
      
    count = 0; 
    while (N--) {
        cin >> now;  //输入菜的好吃程度
        if (count>0) {  //总的好吃度为正时
            if (now >= 0)  //好吃度为正，累加好吃度
                count += now;
            else {
                ss.push_back(count);   //好吃度为负，把之前总的好吃度存下来，并更新总的好吃度
                count = now;
            }
        }
         
        else if (count<0) {  //总的好吃度为负数时
            if (now >= 0) {
                    ss.push_back(count);  //当前好吃度为正，把之前总的好吃度存下来，并更新总的好吃度
                count = now;
            }
            else
                count += now;   //好吃度为负，累加好吃度
        }
         
        else
            count += now;   //总的好吃度为0时，累加好吃度
    }
     
    if (count>0)   //完成数据输入后，总的好吃度如果为正，那么存下来
    {
        ss.push_back(count);
    }
    /*
    上面代码干的活其实简单理解就是把菜的好吃度进行简单的处理：遇到连着正的或者连着负的就累加
    举几组例子方便理解：
    输入：7 7 【1 2 3 -2 3 -10 3】
    输出ss:[6 -2 3 -10 3]
    输入：10 1 【-1 2 4 -3 5 -7 11 24 -6 -9】
    输出ss:[-1 6 -3 5 -7 35]
    输入：6 1 【1 -2 -3 -4 -5 -6】
    输出ss：[1]
    输入：7 1 【1 -1 -2 -3 -4 2 3】
    输出ss：[1 -10 5]
    这样做的目的可以有效减少接下来二维dp的运算量
    否则本题直接用dp会因为运算量过大只通过80%的测试案例
    */
     
    sum = 0;
  
        N = ss.size()+1;
        count = 0;
    //可操作次数大于存储下来的总好吃值个数，直接把正的都取出来累加就是最终的总的好吃度
    if(N<=M){
        for (int j = 0; j < N; j++){
            if(ss[j]>0)
                count+=ss[j];
        }
        return 0;
    }
     
    //可操作次数小于存储下来的总的好吃值的个数，转换为二维dp
    else{
        for (int i = 1; i <= M; i++) {
            sum = 0;
            k=i&1;
            h=(i-1)&1;
            dp[k][0] = 0;
            for (int j = 1; j < N; j++) {
                sum = max(sum, dp[h][j - 1]);
                dp[k][j] = max(sum , dp[k][j - 1]) + ss[j-1];
            }
        }
        for(int i=M;i<N;i++)
        if (count < dp[k][i])
                    count = dp[k][i];
    }
        cout << count << endl;
  
      
    return 0;
  
}

	

同样的思路，java过不了，cpp能过，java不配刷题？

import java.util.*;
/*
和leetcode188，买卖股票的最佳时机Ⅳ类似
将菜价数组改为每一个位置都是前面所有数字的和就和股价一样
一共能进行M次买卖

1. 使用动态规划
状态量有三种，菜的位置i，能打多少次菜M，是否打这个菜s（0或1）
2. 状态转移方程：
dp[i][M][0]=max(dp[i-1][M][0], dp[i-1][M][1])
解释：
    第i个菜不打能获得的最大值为
    上一个菜不打能获得的最大值
    上一个菜打能获得的最大值
    其中较大的一个
dp[i][M][1]=max(dp[i][M][1]+A[i], dp[i][M-1][0]+A[i])
解释：
    第i个菜打能获得的最大值为
    上一个菜也打获得的最大值加上这个菜的值
    上一个菜不打获得的最大值加上这个菜的值，但是上一个菜的M值要-1，因为这个菜要消耗一次打饭机会

3. 初始值
dp[0][M][0]=0
dp[0][M][1]={    0    ,    M=0
                 A[0] ,    M>0}
4. 简化
简化状态转移方程：
dp_i_0[M]=max(dp_i_0[M], dp_i_1[M])
dp_i_1[M]=max(dp_i_1[M]+A[i], dp_i_0[M-1]+A[i])

简化M的值：
对于任意N个菜，只要M > N/2，就能确保打到所有正数的菜
比如N=2,M只要1
N=3，M只要2
N=4，M只要2

简化A数组
连续的几个正值或者负值可以将其合并为1个值，
比如1，1，-1，-1，2，3
可以简化为2，-2，5
*/
public class Main {
    public static void main(String[] args) {
        // 获取输入
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();

        int[] A = new int[N];
        int count = 0;
        int sum = 0;
        // 获取数组A并简化
        for (int i = 0; i < N; ++i) {
            int temp = scanner.nextInt();
            // 若sum和A同号，累加
            if ((sum >= 0 && temp >= 0) || (sum <= 0 && temp <= 0)) {
                sum += temp;
            } else {
                // 否则，加入A，重新累计
                A[count] = sum;// 直接在A数组修改就可以
                ++count;
                sum = temp;
            }
        }
        // 最后一个累计加入数组
        A[count] = sum;
        N = count + 1;

        // 若M > (N + 1) / 2，直接将所有正数累加输出
        if (M > (N + 1) / 2) {
            long result = 0;
            for (int a : A) {
                result += (a > 0 ? a : 0);
            }
            System.out.println(result);
            return;
        }

        // 否则进行dp
        long[] dp_i_0 = new long[M + 1];
        long[] dp_i_1 = new long[M + 1];
        for (int m = 1; m <= M; ++m) {
            dp_i_1[m] = A[0];
        }

        for (int i = 1; i < N; ++i) {
            for (int m = 1; m <= M; ++m) {
                dp_i_0[m] = Math.max(dp_i_0[m], dp_i_1[m]);
                dp_i_1[m] = Math.max(dp_i_1[m] + A[i], dp_i_0[m - 1] + A[i]);
            }
        }

        System.out.println(Math.max(dp_i_0[M], dp_i_1[M]));
    }
}


/*改写成cpp就能过
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int N, M;
    cin>>N;
    cin>>M;
    vector<int> A;
    int sum = 0;
    while (N) {
        --N;
        int temp;
        cin >> temp;
        if ((sum >= 0 && temp >= 0) || (sum <= 0 && temp <= 0)) {
            sum += temp;
        } else {
        // 否则，加入A，重新累计
            A.push_back(sum);// 直接在A数组修改就可以
            sum = temp;
        }
    }
    N = A.size();

    // 若M > (N + 1) / 2，直接将所有正数累加输出
    if (M > (N + 1) / 2) {
        int result = 0;
        for (int a : A) {
            result += (a > 0 ? a : 0);
        }
        cout << result;
        return 0;
    }

        vector<int> dp_i_0(M + 1, 0);
        vector<int> dp_i_1(M + 1, 0);
        for (int m = 1; m <= M; ++m) {
            dp_i_1[m] = A[0];
        }

        for (int i = 1; i < N; ++i) {
            for (int m = 1; m <= M; ++m) {
                dp_i_0[m] = max(dp_i_0[m], dp_i_1[m]);
                dp_i_1[m] = max(dp_i_1[m] + A[i], dp_i_0[m - 1] + A[i]);
            }
        }

        cout << max(dp_i_0[M], dp_i_1[M]);

    return 0;
}
*/

#include<iostream>
#include<stdio.h>
#include<vector>
#include<set>
using namespace std;

/*
    参考(抄袭、借鉴、学了)胡船长的代码  做了注释


    最大m段和
    1.通过合并连续正数、负数，得到正负交错的序列
    2.如果M大于正数数目，答案就是其和
    3.否则可将正数们视为一个段，得到超过M的段数
    4.开始对正数进行合并、舍弃，直到剩余M个正数段结束
        合并、舍弃过程：
            将所有值按绝对值大小全
            每次取最小值出来，如果是正数，则舍弃它，将它与两边负数合并，段数减1
                           如果是负数，则将它视为链接左右两边比它大的正数段的枢纽，合并两边正数
                           
*/
const int max_N = 100005;
struct Node{
    int val;//子段值
    int flag;//是否已被删除
    int l,r;//左边、右边节点的位置
	Node(){}
    Node(int l_,int r_,int val_):l(l_),r(r_),val(val_),flag(0){}
	friend ostream& operator<<(ostream& out,const Node &n){
		out<<"["<<n.l<<" "<<n.val<<" "<<n.r<<" "<<":"<<n.flag<<"]"<<",";
		return out;
	}
};

vector<Node> A(max_N);
void del(int p){
	if(p==0) return ;
    A[p].flag = 1;
    //将其左右连接，有点像链表的删除
    A[A[p].l].r = A[p].r;
    A[A[p].r].l = A[p].l;
    A[p].l=0;
    A[p].r=0;
}
int main(){
	//freopen("temp.in","r",stdin);
    int N,M;
	cin>>N>>M;
	A[0]=Node(0,1,0);
	int a;
    for(int i=1;i<=N;i++){
		cin>>a;
		A[i]=Node(i-1,i+1,a);
    }
	A[N+1]=Node(N,0,0);
	set<pair<int,int> >S; //不用map是因为map按key排序唯一，用pair能保证存在多个val值的node
	
    //合并连续正数、负数
    int p = 1;
    int cnt=0,sum=0;//合并后正数的个数、总和
    while(p!=0){
        while(A[p].r and A[p].val*A[A[p].r].val>=0){
            A[p].val+=A[A[p].r].val;
            del(A[p].r);//数组内不好删除，仅仅作标记，并将其左右相邻点互相链接
        }
        if(A[p].val>0) cnt++,sum+=A[p].val;
        S.insert(make_pair(abs(A[p].val),p));//将所有数按绝对值入堆
        p = A[p].r;
    }

    //可看做现在有cnt段正数，超过M，所以要进行合并或舍弃()，以达到M段
    while(cnt>M){
        auto a = S.begin();//取出正数、负数绝对值中最小的一个(map内部是排序的)
        S.erase(a);
        p = a->second;
		if(A[p].flag) continue;
		//最小数是正数时考虑舍弃掉，跟左右两边的负数合并成一个更大的负数，
		//最小数如果是负数则用来串联左右两边比它大的正数，作为周围两个正数的枢纽  
		
		if((A[p].l==0&nbs***bsp;A[p].r==0) and A[p].val<0) del(p);//最小值是边缘且是负数，直接删除
		else{
			cnt--;
			
			sum-=abs(A[p].val);//加上负数相当于减绝对值，正数也可以直接减
			//串联上左右两边
			A[p].val+=A[A[p].r].val;
			A[p].val+=A[A[p].l].val;
            //删除左右两边
			del(A[p].r);
			del(A[p].l);
            //重新入堆，因为有可能作为枢纽
			S.insert(make_pair(abs(A[p].val),p));
		}
    }
    printf("%d\n",sum);
    return 0;
}

详细解析：
https://blog.csdn.net/FlushHip/article/details/83822873

/*
m段子段的最大和问题
先把整个数组a改成正负交错的数组b，去掉首尾的负数(相邻的正数合并成一个正数，负数合并成一个负数)
动态规划求解
dp[m][j]表示 以j结尾的 m段子段的 最大和
        等于 以下情况的最大值：(m-1)段以0,1,2...j-1结尾的子段 、m段以j-1结尾的子段
dp[m][j] =  max{ dp[m-1][0],dp[m-1][1],...,dp[m-1][j-1],   dp[m][j-1] }

本题卡常数，相同程序，有时服通过，有时不通过，或者优化某些不改变时间复杂度的步骤后通过
另外发现一个诡异的事：64行改为for(j=1,···)，通过；改为j=i，超时 。不懂为什么
*/
#include<bits/stdc++.h>
using namespace std;
#define N 100000
int dp[2][N] = {0};

int main()
{
//    freopen("input.txt", "r", stdin);
    int n, m, i, j, t, tmp;
    scanf("%d%d", &n, &m);
    // 以下构造正负交错的数组 b
    int a;
    vector<int> b;
    b.push_back(0);
    int flag = 0 ;  // 0为初始状态，1为正，-1为负
    int tmp_sum = 0;
    for(i = 0; i < n; i++) {
        scanf("%d", &a);
        if(flag == 0) {
            if(a > 0) flag = 1;
            else continue;
        }
        if(flag < 0 && a > 0) {
            b.push_back(tmp_sum);
            tmp_sum = a;
            flag = 1;
        } else if(flag > 0 && a < 0) {
            b.push_back(tmp_sum);
            tmp_sum = a;
            flag = -1;
        } else if(flag > 0 && a >= 0) {
            tmp_sum += a;
        } else if(flag < 0 && a <= 0) {
            tmp_sum += a;
        }
    }
    if(tmp_sum > 0) b.push_back(tmp_sum);
    int len_b = b.size();

    // 动态规划求解 m段子段的最大和
    memset(dp, 0, sizeof(dp));
    int ans = 0;
    if(m >= len_b / 2) {
        for(int i = 1; i < len_b; i += 2) {
            ans += b[i];
        }
        printf("%d\n", ans);
        return 0;
    }
    for(i = 1; i <= m; i++) {
        int tmp = 0;
        t = i & 1;
        for(j = 1 + (i - 1) * 2; j < len_b - (m - i); j++) {
            tmp = max(tmp, dp[1 - t][j - 1]);
            dp[t][j] = b[j] + max(tmp, dp[t][j - 1]);
        }
    }
    for (j = 1 + (m - 1) * 2; j < len_b; j += 2) {
        ans = max(ans, dp[m & 1][j]);
    }
    printf("%d\n", ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int dp[2][100000];

int main(){
    int n, m;
    cin>>n>>m;
    int a[n], s=0, t=0;
    vector<int> v;
    v.push_back(0);
    int p = 0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(p==0){
            if(a[i]>0)
                p = 1;
            else
                continue;
        }
        if(p<0 && a[i]>0){
            v.push_back(t);
            t = a[i];
            p = 1;
        }else if(p>0 && a[i]<0){
            v.push_back(t);
            t = a[i];
            p = -1;
        }else if(p>0 && a[i]>=0)
            t += a[i];
        else if(p<0 && a[i]<=0)
            t += a[i];
    }
    if(t>0)
        v.push_back(t);
    
    int l = v.size();
    memset(dp, 0, sizeof(dp));
    if(m>=l/2){
        for(int i=1;i<l;i+=2)
            s += v[i];
        cout<<s<<endl;
    }else{
        for(int i=1;i<=m;i++){
            t = 0;
            int k = i&1;
            for(int j=1+(i-1)*2;j<l-(m-i);j++){
                t = max(t, dp[1-k][j-1]);
                dp[k][j] = v[j] + max(t, dp[k][j-1]);
            }
        }
        for(int j=1+(m-1)*2;j<l;j+=2)
            s = max(s, dp[m&1][j]);
        cout<<s<<endl;
    }
    return 0;
}

#include <iostream>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    int *a = new int[N];
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }
    int *b = new int[N+1];
    b[0] = 0;
    int *c = new int[N+1];
    c[0] = 0;
    int sum = 0;
    for(int i = 1; i <= M; i++){
        b[i] = b[i-1] + a[i-1];
        c[i] = b[i];
        for(int j = i + 1; j <= N - M + i; j++){
            b[j] = b[j-1] > c[j-1]? b[j-1] + a[j-1]: c[j-1] + a[j-1];
            sum = sum > b[j]? sum : b[j];
        }
        for(int j = i + 1; j <= N - M + i; j++){
            c[j] = c[j-1] > b[j]? c[j-1] : b[j];
        }
    }
    cout << sum << endl;
    delete a, b, c;
    return 0;
}

def KS16():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))

    b = [0]*(N+1)
    c = [0]*(N+1)

    ans = 0
    for i in range(1,M+1):
        b[i] = b[i-1]+a[i-1]
        c[i] = b[i]
        for j in range(i,N-M+i+1):
            b[j] = max(b[j-1],c[j-1])+a[j-1]
            ans = max(ans,b[j])
        for j in range(i,N-M+i+1):
            c[j] = max(c[j-1],b[j])
    print(ans)

if __name__ == '__main__':
    KS16()

import java.io.*;
import java.util.*;
/*                    t3 (t3 > t2, 合并 b2 至 t3, 合并后如果次数还有多，
*        t1           /\  就要把合并损失的还回去，记录栈内所有 bi-1 - ti)        
*   t0   /\     t2   /
*    \  /  \    /\  /
*     \/    \  /  \/
*     b1     \/   b3
*            b2 (b2 < b1, 截断 t1 至 b2部分，因为这段负数影响已经大于之前的总和，
*                记录栈内所有 ti - bi)
*/
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int N = Integer.parseInt(line[0]);
        int M = Integer.parseInt(line[1]);
        line = br.readLine().split(" ");
        int[] dish = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            dish[i] = dish[i - 1] + Integer.parseInt(line[i - 1]);
        }
        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((n1, n2)-> n2 - n1);
        Deque<Integer> bs = new LinkedList<>();
        Deque<Integer> ts = new LinkedList<>();
        int n = N + 1, b, t = 0, res = 0;
        while (t < n) {
            // 找极小值
            for (b = t; b < n - 1 && dish[b + 1] <= dish[b]; b++) {}
            // 找极大值
            for (t = b + 1; t < n && dish[t - 1] <= dish[t]; t++) {}
            // 截断情况
            while (!bs.isEmpty() && dish[b] < dish[bs.peek()]) {
                maxHeap.add(dish[ts.pop() - 1] - dish[bs.pop()]);
            }
            // 合并情况
            while (!ts.isEmpty() && dish[t - 1] > dish[ts.peek() - 1]) {
                maxHeap.add(dish[ts.pop() - 1] - dish[b]);
                b = bs.pop();
            }
            // 入栈
            bs.push(b);
            ts.push(t);
        }
        // 处理余下部分
        while (!bs.isEmpty()) {
            maxHeap.add(dish[ts.pop() - 1] - dish[bs.pop()]);
        }
        
        while (M-- > 0 && !maxHeap.isEmpty()) {
            res += maxHeap.poll();
        }
        System.out.println(res);
    }
}

import sys

lines = sys.stdin.readlines()
N, M = map(int, lines[0].strip().split())
A = list(map(int, lines[1].strip().split()))

'''
将连续的正数和负数合并
'''
j = 0
length = len(A)
while j < length:
    if A[j] < 0:
        k = j + 1
        while k < length and A[k] < 0:
            A[j] += A[k]
            A.pop(k)
            length = len(A)
    else:
        k = j + 1
        while k < length and A[k] >= 0:
            A[j] += A[k]
            A.pop(k)
            length = len(A)
    j += 1

A.insert(0, 0)
dp_includeJ = [0] * len(A) # 前j个元素的最大子段和，包含j
dp_excludeJ = [0] * len(A) # 前j个元素的最大子段和，不包含j

love = 0

if N <= M:
    for i in range(1, len(A)):
        if A[i] >= 0:
            love += A[i]
else:
    for i in range(1, M + 1):
        love = -float("inf")
        for j in range(i, len(A)):
            # dp_includeJ[j - 1] + A[j] 代表A[j]不是单独的第i段，它是包含在前面的
            # dp_excludeJ[j - 1] + A[j] 代表A[j]是单独的第i段，用前面i-1段的最大子段和 + A[j]
            dp_includeJ[j] = max(dp_includeJ[j - 1], dp_excludeJ[j - 1]) + A[j] # 这里的dp_excludeJ[j - 1]使用的是（i-1）
            # 段的不包含A[j-1]的最大子段和

            dp_excludeJ[j - 1] = love # 这里的dp_excludeJ[j - 1]，是i段的，不包含A[j - 1]的最大子段和，用作最外层循环使用
            if dp_includeJ[j] > love:
                love = dp_includeJ[j]

print(love)

import java.util.Scanner;
//只能通过80%😂 public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        while(input.hasNext()) {
            int N = input.nextInt();
            int M = input.nextInt();
            int[] rank = new int[N];
            for(int i = 0; i < N; i++) {
               rank[i] = input.nextInt();
            }
            System.out.println(Solution(N, M, rank));
        }
        input.close();    
    }
     
    public static int Solution(int N, int M, int[] rank){
        int[] dp = new int[N+1];
        int[] pre_max = new int[N];
        for(int i = 1; i < M + 1; i++){
            for(int j = 1; j < N + 1; j++){
                dp[j] = rank[j-1] + ((dp[j-1] > pre_max[j-1]) ? dp[j-1] : pre_max[j-1]);
                if(j > 1) pre_max[j-1] = (pre_max[j-2] > dp[j-1]) ? pre_max[j-2] : dp[j-1];
            }
        }
        int max = dp[0];
        for(int i = 0; i < N + 1; i++) {
        	if(dp[i] > max) {
        		max = dp[i];
        	}
        }
        return max;
    }
}

80%超时请求大佬帮忙！！！！！！！ 运行超时:您的程序未能在规定时间内运行结束
         请检查是否循环有错或算法复杂度过大。 万分感谢！！