This problem can be solved in O(n log n).
Basic idea
In this explanation, a lot of off-by-one errors probably sneaked in, but it does not matter for the idea. Let m be the minimum of the array. Then any subarray that contains m would have m as a minimum, and every other sub-array would be either entirely before or entirely after m. Let n be the number of elements in the array, and let us treat m as an index. Then for every i < m let's count the subarrays that contain i'th element and have m'th element as a minimum. It is exactly i * (n - m), as there are i possible left edges before i and (n - m) possible edges after m. Each of such arrays would have A[m] as a minimum, and each element with i < m would contribute to the resulting sum with a factor of i * A[m] * (n - m). For i > m with similar reasoning we would get (n - i) * A[m] * m. Then we would update the array before m and after m recursively and then just loop over to get the result.
The problem is in the update. To add these i * A[m] * (n - m) to every possible i would result in a quadratic solution. But as one can notice, both sides are linear functions with respect to i, and this is an important property. Let's rewrite the function for the right side as i * -A[m] * m + n * A[m] * m. So we would use a * i + b expression for every index. If we have two linear functions a * i + b and c * i + d, their sum would, obviously, be (a + c) * i + (b + d) - also a linear function. To conclude this optimization we would use a recursive function with two parameters: subarray currently processed and linear function to apply to each element.
The last problem to solve is finding the minimum in the subarray, but that is known as RMQ problem and can be solved in O(n log n).
The function
To speed things up we would not create subarrays, of course, but pass indices. The pseudocode for what we would like to achieve:
//This uses inclusive l and exclusive r
public int program(int[] A, int l, int r, int a, int b) {
if (r - l == 0) {
//array of size 0 can appear in recursive calls
//if smallest element is first or last in its subarray
return 0;
}
if (r - l == 1) {
//for size one array there exists only one possible subarray
//we also need to add the linear function
return A[l] * A[l] + A[l] * (a * l + b);
}
//This is the call to your RMQ data structure
int m = findMinIdxInSubArray(A, l, r);
int result = 0;
//to the left function would be (i + 1 - l) * A[m] * (r - m) which expands to
//i * A[m] * (r - m) + (1 - l) * A[m] * (r - m)
result += program(A, l, i, a + A[m] * (r - m), b + (1 - l) * A[m] * (r - m));
//to the right function would be (r - i) * A[m] * (m - l + 1) wich expands to
//i * -A[m] * (m - l + 1) + r * A[m] * (m - l + 1)
result += program(A, m + 1, r, a - A[m] * (m - l + 1), b + r * A[m] * (m - l + 1));
//This is the case for the element m itself,
//as it is not accounted in the previous calculations
//the linear function also needs to be accounted here
result += A[m] * (m - l + 1) * (r - m) + A[m] * (a * m + b);
return result;
}
Now your old function would be written like:
public int program(int A[], int n) {
//initialize your RMQ data structure here
return program(A, 0, n, 0, 0);
}
Note that this implementation lacks the findMinIdxInSubArray function, as i mentioned, any RMQ data structure can be used here. Feel free to use anything from Fenwick tree to sparse table.
Example
To explain this formulas a little bit better i would trace the execution of this program for an array A={3,2,1,4}
When the function is first called it has subarray from 0 inclusive to 4 not inclusive and no elements are accounted for now. The minimum of this subarray is element 1 at index 2, and m=2 therefore.
1 is minimum for all subarrays [i,j] such that i <= 2 and 2 <= j.
For element 4 to the right of 1 it appears in 3 arrays ([0,3], [1,3], [2,3]), and recursive call with function -3 * i + 12 would be called. In this function call it is the array of size one, so we would account for subarray {4} with 16 and as it is index 3, it's linear function value is -3 * 3 + 12 = 3, so we would also add 4 * 3 = 12 to account for the arrays from the first function call.
For element 1 itself, it appears in 6 arrays ([0,2],[0,3],[1,2],[1,3],[2,2] and [2,3]) and in the last formula would be added as 1 * 3 * 2 as expected, contributing 6 to the total sum.
Now for the harder array to the left. Element 3 appears in exactly 2 such arrays ([0,2] and [0,3]) and would contribute with a factor of 2 (2 arrays multiplied by minimum value 1 each) and element 2 appears in exactly 4 such arrays([0,2], [0,3], [1,2] and [1,3]). For these two elements, we would call a program with a linear function of 2*i+2, which, as one can see, matches their contribution.
In this recursive call, we would find that 2 at index 1 is the smallest element.
To the right of it, there are no elements, so the recursive call would return 0. 2 itself appears in two subarrays ([0,1] and [1,1]) and from them, it would contribute 8 (2 arrays value 2 in sum and 2 is minimum) to the total sum. But linear function mentions that we should also add 21+1=4 arrayminimums from the previous levels, which matches our computations previously with the contribution of 8. So for 2, we would add a total of 16 in this iteration.
To the left of the two, there is only one element, it is three, it appears in only one array, so its contribution factor should increase by 2 (one array, but minimum is two). The function passed recursively would be (2*i+2) + (2*i+2) = (4*i+4). When we would process the subarray of one element 3 we would add contribution of 9 from the subarray {3} and another 3*(4*0+4) to account for arrays on previous levels, and total contribution would be another 21.
Therefore, recursive function would yield a sum of 21+16+6+28=71. Now lets validate this result by hand:
{3} - min=3, sum=3, min*sum=9
{3,2} - min=2, sum=5, min*sum=10
{3,2,1} - min=1, sum=6, min*sum=6
{3,2,1,4} - min=1, sum=10, min*sum=10
{2} - min=2, sum=2, min*sum=4
{2,1} - min=1, sum=3, min*sum=3
{2,1,4} - min=1, sum=7, min*sum=7
{1} - min=1, sum=1, min*sum=1
{1,4} - min=1, sum=5, min*sum=5
{4} - min=4, sum=4, min*sum=16
Total: 9+10+6+10+4+3+7+1+5+16=71
Edit
If making stack size bigger is not possible to make recursion work, here is the same idea, but without using recursion:
//This uses inclusive l and exclusive r
public int program(int[] A) {
//for every possible l we would store all other call parameters
//in the deepest call with this l
int[] r = new int[A.length];
int[] a = new int[A.length];
int[] b = new int[A.length];
r[0] = A.length;
a[0] = 0;
b[0] = 0;
int result = 0;
for (int l = 0; l < A.length; ++l) {
//this loop would go down recursive calls to
//the deepest call with the same l
while (r[l] - l > 1) {
int m = findMinIdxInSubArray(A, l, r[l]);
//adding to center element
r[m] = m + 1;
//everything that was previously added to the result
//should be stored in a and b
a[m] = a[l];
b[m] = b[l] + (m - l + 1) * (r - m);
//right recursion step
r[m + 1] = r[l];
a[m + 1] = a[l] - A[m] * (m - l + 1);
b[m + 1] = b[l] + r * A[m] * (m - l + 1);
//left recursion step
r[l] = m;
a[l] = a[l] + A[m] * (r - m);
b[l] = b[l] + (1 - l) * A[m] * (r - m)
}
result += A[l] * (a[l] * l + b[l]);
}
