【每日算法Day 98】贪心拼接后和最大的子数组🚩

题目描述

首先输入两个数n和m，接下来输入n个连续的数组中的数。m表示可以将数组重复拼接多少次，求出拼接后的数组中和最大的子数组。

示例

输入：5，1，[1,3,-9,2,4]
输出：6
解释：和最大的子序列为2，4

输入：5，2，[1,3,-9,2,4]
输出：10
解释：和最大的子序列为2，4，1，3

解题思路

输入数组时统计数组中数字的总和sum。m>=2时，先从2X数组拼接的结果中寻找和最大的子数组和total，如果sum<=0，那么拼接两个以上的数组没有意义，如果sum>0，那么要求的值为total+(m - 2) * sum。m=1的情况要单独讨论。（其实这个思路有漏洞，2X数组拼接的和最大的子数组不一定就是在首尾）。

找和最大的子数组的过程使用到了前缀和技巧。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int m = in.nextInt();
            int[] s = new int[n * 2];
            int sum = 0;
            for(int i = 0; i < n; i++){
                s[i] = in.nextInt();
                s[n + i] = s[i];
                sum += s[i];
            }
            //使用前缀和数组去寻找最长序列的和
            long[] prefix = new long[n * 2 + 1];
            for(int i = 1; i <= 2 * n; i++){
                prefix[i] = prefix[i - 1] + s[i - 1];
            }
            
            long max = 0;
            if(m == 1){//如果仅复制一次那么就从只寻找一半的数组
                for(int i = 0; i < n; i++){
                    for(int j = i + 1; j <= n; j++){
                        max = Math.max(max, prefix[j] - prefix[i]);
                    }
                }
                System.out.println(max);
            }else{
                for(int i = 0; i < n * 2; i++){
                    for(int j = i + 1; j <= n * 2; j++){
                        max = Math.max(max, prefix[j] - prefix[i]);
                    }
                }
                if(sum <= 0){
                    System.out.println(max);
                }else{
                    long result = max + (m - 2) * sum;
                    System.out.println(result);
                }
            }
            
        }
    }
}