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.
Step 1: Start
Step 2: Create a variable N to store size of the Dragon and get its value
Step 3: Create an integer array A to store the Dragon's body and get the values for each element
Step 4: Create a variable K to store size of the spell and get its value.
Step 5: Create a new integer variable x=0
Step 6: Create two integer variable i=x+0 and sum_of_damage=0
Step 7: Add the value in ith element in array to sum_of_damage i.e sum_of_damage=sum_of_damage + A[i+x]
Step 8: Repeat Step 6 and Step 7 for different values of i=x+1 to i=x+k-1
Step 9: Increment the value of x by 1 i.e x=x+1
Step 10: Create a variable max to store the maximum damage value and store the value of sum_of_damage in it i.e max=sum_of_damage
Step 10: If x+k<n, Repeat Step 5 to Step 9 to calculate the value for sum_of_damage. If sum_of_damage>max assign the value of sum_of_damge to max i.e max=sum_of_damage
Step 11: Return the value of max
Step 12: Stop