1 连续子数组最大和

一看题干就想到了leetcode 53,还先做了一遍

最开始想的就是用x挨个替换，但是感觉有点...暴力，担心超时。然后就思考好久也没想出来别的方法，最后还是这样写了，发现没有超时

这道题告诉我：想清楚再动笔是一回事儿，没更好的思路直接写就完了

import java.util.*;
import java.util.Arrays;
public class Main {
    public static int greedy(int[] arr, int res) {
        int[] arrSum = new int[arr.length];
        arrSum[0] = arr[0];
        if (arr[0] > res) {
            res = arr[0];
        }
        
        for (int j = 1; j < arr.length; j ++) {
            if (arrSum[j - 1] > 0) {
                arrSum[j] = arrSum[j - 1] + arr[j];
            } else {
                arrSum[j] = arr[j];
            }
            
            if (arrSum[j] > res) {
                res = arrSum[j];
            }
        }
        
        return res;
    }
    
    public static int process(int[] arr, int x) {
        int res = Integer.MIN_VALUE;
        // 不替
        res = greedy(arr, res);
        
        // 替
        for (int i = 0; i < arr.length; i ++) {
            int origin = arr[i];
            arr[i] = x;
            res = greedy(arr, res);
            arr[i] = origin;
        }
        
        return res;
    }
    
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < t; i ++) {
            int n = scanner.nextInt();
            int x = scanner.nextInt();
            int[] arr = new int[n];
            int sum = 0;
            for (int j = 0; j < n; j ++) {
                arr[j] = scanner.nextInt();
            }   
            System.out.println(process(arr, x));
        }
    }
}

2 精华帖子

滑动窗口而已，感觉用前缀和也很简单

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        
        int[] arr = new int[n];
        
        for (int i = 0; i < m; i ++) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            
            for (int j = l; j < r; j ++) {
                arr[j] = 1;
            }
        }
        
        int res = 0;
        
        // 滑动窗口
        for (int i = 0; i < k; i ++) {
            if (arr[i] == 1) {
                res += 1;
            }
        }

        int tempRes = res;
        for (int i = k; i < arr.length; i ++) {
            // i代表新进来的最右边，i - k代表刚出去的最左边
            if (arr[i] == 1) {
                tempRes ++;
            }
            
            if (arr[i - k] == 1) {
                tempRes --;
            }
            
            if (tempRes > res) {
                res = tempRes;
            }
            
            if (res == k) {
                System.out.println(res);
                return;
            }
        }
        
        System.out.println(res);        
    }
}

3 小红的数组构造

用int时候，对于用例：4140 4935 输出了一个负数，于是把int 改为 long了

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        
        long sum = 0;
        long num = 0;
        for (int i = 0; i < n; i ++) {
            num += k;
            sum += num;
        }
    
        System.out.println(sum);
    }
}