划分数组

[编程题]划分数组

热度指数：231 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组arr长度为N，你可以把任意长度大于0且小于N的前缀作为左部分，剩下的作为右部分。但是每种划分下都有左部分的最大值和右部分的最大值，请返回最大的，左部分最大值减去右部分最大值的绝对值。

输入描述:

第一行输入一个整数N(N<100000)
第二行输入N个整数表示arr

输出描述:

输出左部分最大值减去右部分最大值的绝对值的最大值

示例1

输入

5
3 5 1 4 2

输出

说明

5-2

算法知识视频讲解

龙虽无意逐鹿

import java.beans.beancontext.BeanContext;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.StreamTokenizer;

public class Main {
    public static int n = 100001, arr[] = new int[n], left[] = new int[n], right[] = new int[n];

    public static void 预处理() throws IOException {
        n = nextInt();
        int max = 0;
        for (int i = 1; i <= n; i++) {
            arr[i] = nextInt();
            max = Math.max(max, arr[i]);
            left[i] = max;
        }
        max = 0;
        for (int i = n; i >= 1; i--) {
            max = Math.max(max, arr[i]);
            right[i] = max;
        }
        max = 0;
        for (int i = 2; i <= n; i++) {
            max = Math.max(max, Math.abs(left[i - 1] - right[i]));
        }
        System.out.println(max);
    }

    public static void 贪心() throws IOException {
        n = nextInt();
        int max = 0;
        for (int i = 1; i <= n; i++) {
            arr[i] = nextInt();
            max = Math.max(max, arr[i]);
        }
        // 如果max在左半部分,则左半部分的最大值必定为max,因此只要使右半部分的最大值尽量小即可
        // 由于右半部分一定会包含最后一个数字,因此右半部分的最大值不可能小于最后一个数字
        // 不妨令右半部分为最后一个数字
        System.out.println(Math.max(max - arr[1], max - arr[n]));
    }

    public static void main(String[] args) throws IOException {
 贪心();
    }

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer sc = new StreamTokenizer(br);
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

    public static int nextInt() throws IOException {
        sc.nextToken();
        return (int) sc.nval;
    }
}

发表于 2023-04-19 22:02:57 回复(0)

Java

叫我小du

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n <= 1) {
            return;
        }
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int res = getDiff(arr);
        System.out.println(res);
    }

    public static int getDiff(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            max = Math.max(num, max);
        }
        return Math.max(Math.abs(arr[0] - max), Math.abs(arr[arr.length - 1] - max));
    }
}

发表于 2021-04-21 10:28:18 回复(0)