Cod sursa(job #2677327)

Utilizator andrei102Pavel Andrei andrei102 Data 26 noiembrie 2020 11:30:45
Problema Secventa 2 Scor 0
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <stdlib.h>
int maxim(int a, int b)
{
    if(a<b)
        return b;
    return a;
}
void maximumSubarray(int n,int *arr,int *sol,int k,FILE *pf1)
{
    FILE *pf2 = fopen("secv2.out.txt","r+");
    if(k == n)
    {
        fprintf(pf2,"1 %d %d",n,sol[n]);
        return;
    }
    int min = sol[1];
    sol[k+1] = maxim(sol[k+1],sol[k+1]-min);
    for(int i=k+2;i<=n;i++)
    {
        if(min>sol[i-k])
            min = sol[i-k];
        sol[i] = maxim(sol[i],sol[i]-min);
    }
    int max = sol[k];
    int i_right = k;
    for(int i=2;i<=n;i++)
    {
        if(max<sol[i])
        {
            max = sol[i];
            i_right = i;
        }
    }
    int i_left = 1;
    int minim = sol[i_left];
    for(int i=2;i<=i_right-k;i++)
    {
        if(minim>sol[i])
        {
            minim = sol[i];
            i_left = i;
        }
    }

    if(i_left == 1 && sol[1]<=sol[2])
        fprintf(pf2,"1 %d %d",i_right,max);
    else
        fprintf(pf2,"%d %d %d",i_left+1,i_right,max);
    fclose(pf2);
}
int main()
{
    FILE *pf = fopen("secv2.in.txt","r+");
    int n,k;
    fscanf(pf,"%d%d",&n,&k);
    int *arr = (int *)malloc(sizeof(int)*(n+1));
    int *sol = (int *)malloc(sizeof(int)*(n+1));
    int sum = 0;
    for(int i=1;i<=n;i++)
    {
        fscanf(pf,"%d",&arr[i]);
        sum+=arr[i];
        sol[i] = sum;

    }
    maximumSubarray(n,arr,sol,k,pf);
    fclose(pf);
    return 0;
}