SeaCode

Appearance

Maximum Absolute Difference ​

Problem Description ​

You are given an array of N integers, A1, A2 ,..., AN.

Return maximum value of f(i, j) for all 1 ≤ i, j ≤ N.

f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.

Problem Constraints

1 <= |A| <= 10^5
-10^9 <= Ai <= 10^9
1 <= |A| <= 10^5
-10^9 <= Ai <= 10^9

Input Format

The first argument is an integer array A.
The first argument is an integer array A.

Output Format

Return an integer equal to the maximum value of f(i, j)
Return an integer equal to the maximum value of f(i, j)

Example Input

A = [1, 3, -1]
A = [1, 3, -1]

Example Output

5
5

Example Explanation

Given A = [1, 3, -1], 
f(1, 1) = f(2, 2) = f(3, 3) = 0
f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3
f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4
f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5
The maximum value is 5, which is of f(2, 3)
Given A = [1, 3, -1], 
f(1, 1) = f(2, 2) = f(3, 3) = 0
f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3
f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4
f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5
The maximum value is 5, which is of f(2, 3)

Solution ​

swift
import Foundation

class Solution {
	func maxArr(_ A: inout [Int]) -> Int {
        let len = A.count
        var result = 0
        
        var min1 = Int.max
        var max1 = Int.min
        
        var min2 = Int.max
        var max2 = Int.min
        
        for i in 0..<len {
            var v = A[i] + i
            if v < min1 {
                min1 = v
            }
            if v > max1 {
                max1 = v
            }
            
            v = A[i] - i
            if v < min2 {
                min2 = v
            }
            if v > max2 {
                max2 = v
            }
        }
        if (max1 - min1 ) > result {
            result = max1 - min1
        }
        
        if (max2 - min2 ) > result {
            result = max2 - min2
        }
        
        
        
        
        // for i in 0..<len {
        //     for j in (i+1)..<len {
        //         let v = abs(A[i] - A[j]) + j - i
        //         if v > result {
        //             result = v
        //         }
        //     }
        // }
        return result
	}
}
import Foundation

class Solution {
	func maxArr(_ A: inout [Int]) -> Int {
        let len = A.count
        var result = 0
        
        var min1 = Int.max
        var max1 = Int.min
        
        var min2 = Int.max
        var max2 = Int.min
        
        for i in 0..<len {
            var v = A[i] + i
            if v < min1 {
                min1 = v
            }
            if v > max1 {
                max1 = v
            }
            
            v = A[i] - i
            if v < min2 {
                min2 = v
            }
            if v > max2 {
                max2 = v
            }
        }
        if (max1 - min1 ) > result {
            result = max1 - min1
        }
        
        if (max2 - min2 ) > result {
            result = max2 - min2
        }
        
        
        
        
        // for i in 0..<len {
        //     for j in (i+1)..<len {
        //         let v = abs(A[i] - A[j]) + j - i
        //         if v > result {
        //             result = v
        //         }
        //     }
        // }
        return result
	}
}

References ​