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

Categories:

题目描述
思路分析
1. 解法一：Kadane + 前后缀最大和（推荐）
相似题目

题目描述

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

思路分析

解法一：Kadane + 前后缀最大和（推荐）

核心思路：

用 Kadane 求单数组最大子数组和 bestOne（允许空子数组，最低为 0）。

计算最大前缀和 bestPrefix、最大后缀和 bestSuffix 以及总和 sum。

当 k == 1 时答案为 bestOne。

当 k > 1 时，跨多数组的最优要么是 bestOne，要么是 bestPrefix + bestSuffix + (k - 2) * sum（仅当 sum > 0 时才叠加）。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度。

空间复杂度：O(1)，只使用常数变量。

class Solution {
    private static final int MOD = 1_000_000_007;

    public int kConcatenationMaxSum(int[] arr, int k) {
        long bestOne = 0;
        long cur = 0;
        for (int v : arr) {
            cur = Math.max(0, cur + v);
            bestOne = Math.max(bestOne, cur);
        }

        long sum = 0;
        long bestPrefix = 0;
        long prefix = 0;
        for (int v : arr) {
            prefix += v;
            bestPrefix = Math.max(bestPrefix, prefix);
            sum += v;
        }

        long bestSuffix = 0;
        long suffix = 0;
        for (int i = arr.length - 1; i >= 0; i--) {
            suffix += arr[i];
            bestSuffix = Math.max(bestSuffix, suffix);
        }

        long ans = bestOne;
        if (k > 1) {
            long cross = bestPrefix + bestSuffix;
            if (sum > 0) {
                cross += (long) (k - 2) * sum;
            }
            ans = Math.max(ans, cross);
        }

        return (int) (ans % MOD);
    }
}

func kConcatenationMaxSum(arr []int, k int) int {
    const mod = 1000000007

    bestOne := int64(0)
    cur := int64(0)
    for _, v := range arr {
        cur = max64(0, cur+int64(v))
        bestOne = max64(bestOne, cur)
    }

    sum := int64(0)
    bestPrefix := int64(0)
    prefix := int64(0)
    for _, v := range arr {
        prefix += int64(v)
        if prefix > bestPrefix {
            bestPrefix = prefix
        }
        sum += int64(v)
    }

    bestSuffix := int64(0)
    suffix := int64(0)
    for i := len(arr) - 1; i >= 0; i-- {
        suffix += int64(arr[i])
        if suffix > bestSuffix {
            bestSuffix = suffix
        }
    }

    ans := bestOne
    if k > 1 {
        cross := bestPrefix + bestSuffix
        if sum > 0 {
            cross += int64(k-2) * sum
        }
        if cross > ans {
            ans = cross
        }
    }

    return int(ans % mod)
}

func max64(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
53. 最大子数组和	简单	Kadane
918. 环形子数组的最大和	中等	前后缀 + Kadane
1031. 两个非重叠子数组的最大和	中等	前缀最大和
1749. 任意子数组和的绝对值的最大值	中等	前缀和
152. 乘积最大子数组	中等	子数组 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/15654451