/***************************************************
* Section : 15
* Machine No. : N
* Roll No. : 18CS100XY
* Name : Soumyajit Dey, Aritra Hazra
* Assignment No : 9b
* Description : Determines Standard Deviation Target
****************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PRECISION 0.000001

int standard_dev(int a[], int i, int k, double m, int *n)
{
    int sum = 0, sum_2 = 0, sdCount = 0, l, j;
    double am, sd, maxSD;
    
    /* calculation for first k-length sunsequences */
    for(j=0; j<k; j++){
        sum += a[j];
        sum_2 += a[j]*a[j];
    }
    am = sum/k;
    sd = sqrt(sum_2/k - am*am);
    if(sd - m >= PRECISION){
        sdCount++;
    }
    maxSD = sd; /* first time maximum SD assignment */
    *n = 0;
    
    /* calculation for remaining k-length subsequences */
    for(l=1; l<=i-k; l++){
        sum = 0; sum_2 = 0;
        for(j=l; j<l+k; j++){
            sum += a[j];
            sum_2 += a[j]*a[j];
        }
        am = sum/k;
        sd = sqrt(sum_2/k - am*am);
        if(sd - m >= PRECISION){ /* admissible SD count */
            sdCount++;
        }
        if(sd - maxSD > PRECISION){ /* determine maximum SD index */
            maxSD = sd;
            *n = l;
        }
    }
    return sdCount;
}

int main()
{
    int *a;
    int n, i, j, k;
    double m;
    
    printf("How Many Integers? ");
    scanf("%d", &i);
    a = (int *)malloc(i*sizeof(int));
    printf("Enter %d Integers: ", i);
    for(j=0; j<i; j++)
        scanf("%d", &a[j]);
    printf("Enter Subsequence Size: ");
    scanf("%d", &k);
    printf("Enter Standard Deviation Value: ");
    scanf("%lf", &m);
    
    if(k>i){ /* subsequence length is more than number of integer data entered */
        printf("-- Warning: Length of Subsequence (k = %d) is MORE than the Number of Integer Data (i = %d)! So, making k = i = %d\n", k, i, i);
        k=i;
    }
    
    printf("++ %d Number of %d Length Subsequences Exist in the Overall %d Length Sequence of Integer Data where SD >= %lf.\n", standard_dev(a, i, k, m, &n), k, i, m);
    printf("++ The Starting Index of %d Length Subsequence whose SD is Maximum = %d.\n", k, n);
    
    return 0;
}