Find sum of product of all possible triplets in an array in O(n)? For example, 
If array A = { 1, 2, 3 ,4 }
possible triplets are {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} and their products are 6, 8, 12, 24 respectively.
So final answer is 50.
I found a O(n) time code, but i can't understand how it is working. 
Initially count1 array stores the original array and all other arrays has only 0 elements.
int sum = 0;

B[n-1] = count1[n];
for(i=n-2;i>=0;i--) 
    B[i] = (B[i+1] + count1[i+1]);

for(i=1;i<n-1;i++) 
    C[i] = (count1[i+1] * B[i+1]);

D[n-2] = C[n-2];
for(i=n-3;i>=1;i--) 
    D[i] = (D[i+1] + C[i]);

for(i=0;i<n-2;i++) 
    sum = (sum + count1[i+1] * D[i+1]);


If Someone wants to know how above code works, 
read this thread : 
https://www.quora.com/How-do-I-find-the-sum-of-products-of-all-possible-k-numbers-from-an-array-of-N-numbers-k-n
 A: The code is a bit more tricky than it needs to be to achieve $O(n)$. Let $\sigma_k=\sum_ix_i^k$ (where the $x_i$ are the numbers). Then you basically want $\frac16\sigma_1^3$, but that counts some products with repeated factors. Products with one factor repeated twice are counted with weight $\frac12$, so we have to subtract $\frac12\sigma_1\sigma_2$, and then products with a single factor cubed are counted with weight $\frac16-\frac12=-\frac13$, so we have to add $\frac13\sigma_3$, for a total of $\frac16\left(\sigma_1^3-3\sigma_1\sigma_2+2\sigma_3\right)$. In your example, $\sigma_1=10$, $\sigma_2=30$ and $\sigma_3=100$, so the result is $\frac16\left(10^3-3\cdot10\cdot30+2\cdot100\right)=50$.
A: Prefix sum Logic:-
Let A = {1, 2, 3 , 4, 5}
Possible triplets = {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}
Calculations of all triplets if we consider 3 as middle element in triplets
= (1 * 3 * 4) + (1 * 3 * 5) + (2 * 3 * 4) + (2 * 3 * 5)
= 3 * (1 * 4 + 1 * 5 + 2 * 4 + 2 * 5)
= 3 * (1 * (4 + 5) + 2 * (4 + 5))
= 3 * (1 + 2)(4 + 5)
This can be rewritten as: (1 + 2) * 3 * (4 + 5) _______ [1]
Calculations of triplets if we consider all elements one by one as the middle element can be computed the same way
[1] signifies that (1 + 2) is the sum of left subarray and (4 + 5) is sum of right subarray.
The main idea is to traverse each element (arr[i]) and add to sum:
(left subarray sum from 0 to i - 1) * arr[i] * (right subarray sum from i + 1 to n - 1)
Pseudo Code:
int tripletsSum(int[] arr){ // {1, 2, 3, 4, 5}
        int n = arr.length, sum = 0;
        int[] pre = new int[n]; // Initialise Prefix sum array
        pre[0] = arr[0]; // Initialize first element as first element of arr
        
        // Computing the whole prefix sum array
        // {1, 3, 6, 10, 15}
        for (int i = 1;i < n;i++) pre[i] = arr[i] + pre[i - 1];

        for (int i = 1;i < n - 1;i++){ 
            sum +=    pre[i - 1]   *   arr[i]   *  (pre[n - 1] - pre[i]);
        }     //    left subarray sum                right subarray sum
        return sum;
    }

Time Complexity = O(N)
Space Complexity = O(N)
A: In  above shared Link, he used dynamic porgramming bottom up approach that difficult to think but easy to implement here i am sharing my top down approach of dp for this concept.. 
    /*
     * To change this license header, choose License Headers in Project Properties.
     * To change this template file, choose Tools | Templates
     * and open the template in the editor.
 */
package EasyProblems;

import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * @author Hemant Dhanuka
 */
public class Sum_OfProduct_Ofall_K_numbers_From_Array {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int N = s.nextInt();
        int a[] = new int[N];
        for (int l = 0; l < N; l++) {
            a[l] = s.nextInt();
        }
        int k = s.nextInt();

        long dp[][] = new long[N][k];
        for (long d[] : dp) {
            Arrays.fill(d, -1);

        }
        //System.out.println(dp[1][1]);
        long ans = sum(a.length - 1, k - 1, a, dp);
        System.out.println(ans);

    }

    static long sum(int n, int k, int a[], long dp[][]) {

        if (k == -1) {
            return 1;
        }

        if (n == -1) {
            return 0;
        }

        if (dp[n][k] != -1) {
            return dp[n][k];
        }
        //if picked
        long ans1 = ((long) a[n]) * sum(n - 1, k - 1, a, dp);

        //if not picked
        long ans2 = sum(n - 1, k, a, dp);
        dp[n][k] = ans1 + ans2;
        return ans1 + ans2;
    }
}

