Problem

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 (0 < P < Q < N - 1, Q - P > 1), resulting in three chains [0, 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 an array such that:

A[0] = 5
A[1] = 2
A[2] = 4
A[3] = 6
A[4] = 3
A[5] = 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
Write a function
class Solution {
public int solution(int[] A);
}
that, given an array A of N integers, returns the minimal cost of dividing the chain into three pieces. Given the example above, the function should return 5.

I want to know optimal solution to this problem

public int solution(int[] A){
int minCost = Int32.MaxValue;
int n = A.Length;
for(int i = 0; i < n - 3;i++) {
for(int j = i+2; j < n-1; j++){
int sum = A[i] + A[j];
minCost = Math.Min(minCost, sum);
}
}
return minCost;
}

Time Complexity for this solution is O(n^2). Need better solution than this one maybe O(NLogN) or O(N)