I came across a question while I was working on DS ,I am able to solve it in O(n^2) ,can someone here think of how it can be done in O(n)?

An array A consisting of N integers is given.

The elements of array A together represent a chain, and each element represents the strength of each link in the chain. We want to divide this chain into three smaller chains.

All we can do is break the chain in exactly two non-adjacent positions. More precisely, we should break links P, Q (O < P < Q < N — 1, Q — P > 1), resulting in three chains [O, P - 1], [P 1, Q - 1] [Q 1, N - 1]. The total cost of this operation is equal to A[P] A[Q] For example, consider array A such that: { 5, 2, 4, 6, 3, 7 }

We can choose to break the following links:

• (1,3) : total cost is 2 6=8
• (1,4) :total cost is 2 3=5
• (2,4): total cost is 4 3=7

Here the minimum cost would be 5,is there a way to do this in O(N)

CodePudding user response：

There's a simple O(N) time and space algorithm, once you break down what the question is asking: We want two non-adjacent array elements, excluding the first and last elements, of minimal sum. You could ignore the first and last elements, and keep a helper array H of the smallest element at or after every index i; then your answer is

Minimum over 1 <= i <= n-4 of: A[i]   H[i 2]

With a little more thought, you can get a linear time, constant space solution. It turns out that you only need to track the location of the four smallest interior elements of the array; this can be done by iterating over all elements and pushing pairs (A[i], i) into a max-heap, which you pop if its size exceeds 4. Then you need to check the four combinations (1,2), (1,3), (1,4), (2,3) and choose the non-adjacent combination with minimum sum.

To see why you need all four smallest, consider an array like [0,8,4,1,7,0], whose minimal pair is 1 8, consisting of the smallest and fourth smallest valid element. At least two of those pairs will be non-adjacent (unless n is 5, in which case, there is a unique valid pair).