K 次串联后最大子数组之和

一、题目描述

题目链接：https://leetcode-cn.com/problems/k-concatenation-maximum-sum/

 

二、题目分析

参考题解：https://leetcode-cn.com/problems/k-concatenation-maximum-sum/solution/java-shi-jian-on-kong-jian-o1-fen-lei-tao-lun-by-g/

按照题目的要求，我们可以想到几种可能得到最大拼接数组和的做法。

1、最大值存在单个数组的中间部分（不与其他数组接触）

2、两个数组拼接在一起，最大后缀和加上最大前缀和得到最大值。

3、k个数组拼接在一起，第一个数组取最大后缀和，最后一个数组取最大前缀和，加上中间夹的数组综合得到最大值。

 

三、代码

public int kConcatenationMaxSum(int[] arr, int k) { int mod = 1000000007; // 计算最大前缀和 int pre = 0; int curr = 0; for (int num: arr) { curr += num; if (curr > pre) pre = curr; } // 计算最大后最和 int post = 0; curr = 0; for (int i = arr.length-1; i >= 0; i --) { curr += arr[i]; if (curr > post) post = curr; } // sum保存数组综合 int sum = 0; // 计算单个数组最大子数组和 int midMax = arr[0]; curr = 0; for (int num: arr) { sum += num; curr += num; if (curr > midMax) midMax = curr; if (curr < 0) { curr = 0; } } if (k == 1) return midMax; return Math.max(midMax,Math.max((pre + post) % mod, (int) ((long) sum * (k-2) % mod + pre + post) % mod)); }