In: Computer Science
Jojo the wizard is currently on a dragon’s lair. To escape from the lair, Jojo needs to defeat the elder dragon. Jojo is currently a wizard under training, so he knows only one spell : the fireball spell. The dragon’s body can be represented as an array of size N , where each part of the dragon’s body, from its head to its tail, is numbered with integer from 1 to N. Each body part has its sensitivity to fire a i . If a i is positive, then the fireball spell will deal a i damage to the dragon. If a i is negative, it will heal the dragon by − a i health points instead.
The fireball spell is a spell which deals damage to the dragon’s body on exactly K consecutive body parts. That is, if Jojo casts the spell on i-th body part, then the fireball will attack the parts [i, i+1, i+2, ..., i + K −1]. For example, if the dragon’s body is [1 , 2 , − 2 , 4 , 5], and K is 3, then Jojo may cast the spell on 1st, 2nd, and 3rd body part, which deals 1, 4, and 7 damage respectively. Jojo can’t cast the spell on 4 or 5 since the fireball must hit exactly K body parts of the dragon. As Jojo can only cast the spell one time, Help Jojo determine the maximum damage output he can deal to the dragon.
Format Input
The first line of the input contains two integers N and K, the number of the dragon’s body part and the range of the fireball spell. The next line consists of N integers a i , the sensitivity of each body part.
Format Output
Output the maximum damage Jojo can deal to the elder dragon. If Jojo can’t deal any damage, output 0 instead.
Constraints
• 1 ≤ K ≤ N ≤ 103
• 0 ≤ | a i | ≤ 109
Sample Input 1 (standard input)
5 3
1 2 -2 4 5
Sample Output 1 (standard output)
7
Sample Input 2 (standard input)
5 1
-1 -2 -3 -4 -5
Sample Output 2 (standard output)
0
Explanation
On the second sample, no matter where Jojo choose to cast his fireball spell, it will heal the dragon. So, the answer to the second sample is 0.
NOTE: USE C LANGUAGE, DONT USE FUNCTION(RESULT,RETURN),VOID,RECURSIVE, USE BASIC CODE AND CODE IT UNDER int main (){, constraint must be the same
Please find your solution below and if doubt comment and do upvote.
CODE:
#include <stdio.h>
int main()
{
int n,k;
//take user input
scanf("%d",&n);
scanf("%d",&k);
//make an array since N is of order 10^3
//long int array is becoz a[i] is of order 10^9
long int arr[10000];
//take user input
for(int i=0;i<n;i++)
{
scanf("%ld",&arr[i]);
}
//to store maximum damage
long int Maxsum=0;
//traverse till n-k index in first loop
// consider every k size subarray and sum them
//then compare and find the Maxsum
for(int i=0;i<n-k+1;i++)
{
long int localMax=0;
//add the subarray of size k
for(int j=i;j<k+i;j++)
{
localMax+=arr[j];
}
//compare and find Maxsum
if(Maxsum<localMax)
Maxsum=localMax;
}
//print the output
printf("%ld",Maxsum);
return 0;
}
OUTPUT: