Sub array Programs in C

Q) Number of sub arrays in a given array and sum of sub array elements.

For example given an array as shown below

23

14

39

42

Subarrays that can be formed are

[23], [23, 14], [23 , 14, 39], [23, 14, 39, 42]

[14], [14, 39], [14, 39, 42]

[39], [39, 42]

[42]

here 0^th index element 23 occurs 4 times as first element in subarray.

1^st index element 14 occurs 6 times of which
3 times it occurs as first element in subarray and
remaining 3 times it occurs in combination with first element 23

 2^nd index element 39 occurs 6 times of which
2 times it occurs as first element in subarray and
2 times it occurs in combination with first element 23
2 times it occurs in combination with second element 14

3^rd index element 42 occurs 4 times of which
1 times it occurs as first element in subarray and
1 times it occurs in combination with first element 23
1 times it occurs in combination with second element 14
1 times it occurs in combination with third element 39

if n is the number of elements in an array, here n=4

23 occurs n-i times as first element where i =0 as 23 is 0^th index element

14 occurs n-i times as first element where i =1 as 14 is 1^st index element.
remaining n-i times it occurs in combination with first element.

39 occurs n- i times as first element where i=2
n-i times in combination with first element 23
n-I times in combination with second element 14….so i *(n-i) times

and so on..

so general formula is

number of times i^th element occurs = (n – i)+ i* (n-i)

Sum of sub array elements = number of times it occurs * element

So the program is:

#include <stdio.h>

int main()

{

               int n;

               printf("enter the number of elements\n");

               scanf("%d",&n);

               int a[n],sum=0,i;

               printf("\nEnter array elements\n");

               for(i=0;i<n;i++)

                              scanf("%d",&a[i]);

               for(i=0;i<n;i++)

               {

                              sum = sum+((n-i)+(n-i)*i)*a[i];

               }

               printf("sum = %d",sum);

}

Output:

Q) find the maximum possible length of subarray In that subarray a[i+1]%a[i]==0 Every element in subarray is divisible by its previous element Your task is to find maximum length of subarray.

#include <stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
{
    int n;
scanf("%d",&n);
    int a[n],i,j,max1=0,res=0,max2;
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
   
    for(i = 0 ; i < n ; i++)
    if(max1 < a[i])
    max1=a[i];
    
    int cnt[max1+1] = {0};
    int dp[max1+1] = {0};
    
    for( i = 0 ; i < n ; i++)
    cnt[ a[i] ]++ ;
    
    for (i = max1 ; i > 0 ; i--)
    {
        max2=0;
        for( j = 2*i ; j <= max1 ; j+=i )
        if(max2<dp[j])
        max2 = dp[j];
            dp[i] = cnt[i] + max2;
    }
    
    
    for( i = 0 ; i < max1+1 ; i++)
    if(res<dp[i])
    res = dp[i];
    printf("%d\n",res);
   
    }
    return 0;

}