'Sum of all elements of each subarray

I was solving Kadane's algorithm , a very weird approach came to my mind while solving it. What if we find a way to find out the sum of all the elements of all possible subarrays forming from an array and store it in an arraylist. I've been thinking about it for a long time now, but I'm unable to solve it. It would be great if I can get some assistance.

`

 import java.util.*;
 import java.lang.*;
 import java.io.*;

class Sample
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        ArrayList<Integer> list = new ArrayList<>();
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=arr[i];
        }
        list.add(sum);
        for(int i=0;i<n;i++){
            list.add(arr[i]);
        }
        for(int i=0;i<n;i++){
            //sum-=arr[i];
            if(!list.contains(sum-arr[i]) && (sum-arr[i])>0){
                list.add(sum-arr[i]);
            }
            sum=sum-arr[i];
        }
        System.out.println(list);
    }
}

`

This is what I've done till now. There's a very big flaw in the logic and I know it but I just can't seem to solve it.

javaarrays


Solution 1:[1]

This doesn't use Kadanes algorithm, but it does sum the sub arrays. It is facilitated by using the subList method of the List interface.

for (int i = 1; i < 8; i++) {
    List<Integer> list =
            IntStream.range(1, i+1).boxed().toList();
    List<Integer> sums = new ArrayList<>();
    findsubs(list, 0, list.size(), sums);
    System.out.println(sums);
    sums.clear();
}

prints

[1]
[3, 2, 1]
[6, 5, 3, 3, 2, 1]
[10, 9, 7, 4, 6, 5, 3, 3, 2, 1]
[15, 14, 12, 9, 5, 10, 9, 7, 4, 6, 5, 3, 3, 2, 1]
[21, 20, 18, 15, 11, 6, 15, 14, 12, 9, 5, 10, 9, 7, 4, 6, 5, 3, 3, 2, 1]
[28, 27, 25, 22, 18, 13, 7, 21, 20, 18, 15, 11, 6, 15, 14, 12, 9, 5, 10, 9, 7, 4, 6, 5, 3, 3, 2, 1]

The method

    
public static void findsubs(List<Integer> list, int s, int e,
        List<Integer> sums) {
    if (s >= e) {
        return;
    }
    for (int i = s; i < e; i++) {
        sums.add(list.subList(i, e).stream()
                .mapToInt(Integer::intValue).sum());
    }
    findsubs(list, s, e - 1, sums);
    
}

Solution 2:[2]

long subarraySum(vector<long> &A) {
    long result = 0;
    int n = A.size();
    for (int i=0; i <n; ++i)
    {
        result +=(A[i]*(i+1)*(n-i));
    }
    return result;
}

Sum of all sub array means, Actually each element how many time contribute himself in each sub array lets take : [1 2 3 4][0,0][0,1][1,1][0,2][1,2][2,2][0,3][1,3][2,3][3,3]

contribution of ith element is A[i](i+1)(n-i)

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 WJS
Solution 2 Anonymous

Related Questions