给定一个长度为N(N>1)的整形数组arr, 可以划分成左右两个部分,左部分为arr[0…K],右部分为arr[K+1…N-1], K可以取值的范围是[0,N-2]。求这么多划分方案中,左部分中的最大值减去右部分最大值的绝对值中,最大是多少
[要求]
时间复杂度为O(n), 空间复杂度为O(n)
第一行一个整数N,表示数组长度。
接下来一行N个整数,表示数组内的数。
输出一个整数表示最优答案
5 2 7 3 1 1
6
当左部分为[2, 7],右部分为[3, 1, 1]时,左部分中的最大值减去右部分的最大值的绝对值为4,。当左部分为[2, 7, 3],右部分为[1, 1]时,左部分中的最大值减去右部分最大值的绝对值为6。还有很多划分方案,但最终返回6.
import scala.io.StdIn object Main { def main(args: Array[String]): Unit = { val in = StdIn val n = in.readInt() val arr = in.readLine().split(" ").map(_.toInt) if(n == 2){ println(math.abs(arr(0) - arr(1))) }else{ val leftMax = Array.ofDim[Int](n) // 前缀最大值 val rightMax = Array.ofDim[Int](n) // 后缀最大值 leftMax(0) = arr(0) rightMax(n - 2) = arr(n - 1) for(i <- 1 until n - 1) leftMax(i) = math.max(arr(i), leftMax(i - 1)) for(i <- n - 3 to 0 by -1) rightMax(i) = math.max(arr(i + 1), rightMax(i + 1)) var max = 0 for(i <- 0 until n - 1) max = math.max(max, math.abs(leftMax(i) - rightMax(i))) println(max) } } }但其实我们还可以把O(N)的空间省掉,并且在常数层面优化O(N)的时间复杂度。由题意可以知道,leftMax和rightMax中一定有个全局最大值max,分如下的两种情况:
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] strArr = br.readLine().split(" "); int[] arr = new int[n]; int max = Integer.MIN_VALUE; for(int i = 0; i < n; i++) { arr[i] = Integer.parseInt(strArr[i]); max = Math.max(max, arr[i]); } System.out.println(Math.max(max - arr[0], max - arr[n - 1])); } }
#include <bits/stdc++.h> using namespace std; int main(){ int n, Max=INT_MIN; cin>>n; int a[n+1], l[n+2], r[n+2]; l[0] = l[n+1] = r[0] = r[n+1] = 0; for(int i=1;i<=n;i++){ cin>>a[i]; l[i] = max(l[i-1], a[i]); } for(int i=n;i>=1;i--){ r[i] = max(r[i+1], a[i]); Max = max(Max, abs(r[i]-l[i])); } cout<<Max<<endl; return 0; }