Sum of Largest Neighbors

ArraySimulation

Given an array of integers, your task is to calculate the sum of the largest direct neighbors for each element in the array. An element's direct neighbors are those elements that are immediately to its left and right in the array. For the elements at the boundaries (start and end of the array), consider only one neighbor.

Example

Input: [1, 3, 2, 4] Output: 9

In this example, for element 3, its neighbors are 1 and 2, and the largest is 3. For 2, the neighbors are 3 and 4, with 4 being the largest. Summing these up gives, 3 (for 1) + 3 + 4 + 4 (for 4) = 14.

Example 1

Input

[
  1,
  2,
  3,
  4
]

Output

Explanation. Here, the sum of the largest neighbors are 2 (for 1) + 3 (for 2) + 4 (for 3) + 4 (for 4) = 13.

Example 2

Input

[
  5,
  1,
  3
]

Output

Explanation. Largest neighbor for 5 is 1, for 1 is max(5,3) = 5 and for 3 is 1. Therefore, the sum is 1 + 5 + 1 = 7.

Example 3

Input

[
  2
]

Output

Explanation. There is only one element, so no neighbors exist, hence sum is 0.

Example 4

Input

[
  4,
  3,
  2,
  1
]

Output

Explanation. Here, the sum of the largest neighbors are 3 (for 4) + 4 (for 3) + 3 (for 2) + 2 (for 1) = 12.

Follow-up: Can you optimize your solution to use less additional space, perhaps modifying the input array itself?

Constraints:

1. The array contains at least 1 and up to 1000 elements. 2. Each element in the array will be an integer ranging from -1000 to 1000.

Views: 2