Pagini recente » Cod sursa (job #2273073) | Cod sursa (job #522413) | Cod sursa (job #191701) | Cod sursa (job #2084717) | Cod sursa (job #2677345)
#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)
{
if(k == n)
{
fprintf(pf1,"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(pf1,"1 %d %d",i_right,max);
else
fprintf(pf1,"%d %d %d",i_left+1,i_right,max);
fclose(pf1);
}
int main()
{
FILE *pf1 = fopen("secv2.in.txt","r+");
FILE *pf2 = fopen("secv2.out.txt","w+");
if(pf1!=NULL && pf2!=NULL)
{
int n,k;
fscanf(pf1,"%d%d",&n,&k);
int arr[100000];
int sol[100000];
int sum = 0;
for(int i=1; i<=n; i++)
{
fscanf(pf1,"%d",&arr[i]);
sum+=arr[i];
sol[i] = sum;
}
maximumSubarray(n,arr,sol,k,pf2);
fclose(pf1);
fclose(pf2);
}
return 0;
}