Infosys SP & DSE Round1 & Round2 Questions | Infosys Hiring |

Added: 2026-05-12

[00:00:01]Hello everyone, welcome to online study for you. My name is Panchi and in today's video we are going to see some of the questions that has already came in the latest Infosys SPDSC questions.

[00:00:11]So we will be doing questions that are difficult and has already came in the latest shift right. So we all know that uh we have got uh round one round one is already done for 2024 and 2025 batches right it is already done on 26th of April and they have started getting the round two call right so you have to if you are from 2024 batch or 2025 batch who has already given round one and who has got this round two mail then you should all start working on the uh second round where you will be ing questions. You have to do the questions and then you will be having your interview on the sim the same day.

[00:00:53]Right? And for the students who are from 2026 batch, you guys are going to have round one very soon. Although the emails are not still out that what is the exact dates of the exam, but you will be getting the dates very soon. So this is the uh exact uh scenario that is happening right now. So we will be taking some of the questions that already came on 26th April by uh shared by some of the students right. So we will be doing those questions and discussing those today in this uh video.

[00:01:26]Now before starting with the lecture I just want to let you know that we have one course with where we have all the um questions like you have DSA in all the languages DSA in Python in Java C++ you have your white book right DSA white book which contains more than 200 questions right you will be having the solutions the questions and everything well arranged so if you are um looking for some course or some thing where you can depend on so this This is the one course which you can definitely check it out. Right? So this is it. Now let's directly move on to the very first question that we are going to discuss today. So the question name is maximum total mode frequency score. Okay. So first of all we will be doing it in a very sequential way. Right? We will be reading the question. We will be understanding what the problem statement says. We will be checking what the input format is, what the input is, what are the constraints. Then we will be having one understanding that okay what is the how we can break because in infosys questions the major portion is that if you understood the question you can actually start doing them but most of the students stuck in not even understanding them right so for each of the questions we will be first of all understanding that what question is asking from us right and then once everything is clear then we will be moving towards the optimal approach that what approach we should take to solve these type of questions and then we will be discussing about the code. So this is the whole template how I'll be uh taking the whole video right. So let's have the very first question. So the question is maximum total mode frequency score. So the problem statement says that you are given an array of from 1 to n and an integer k. So you will be given one array and you will be given integer k.

[00:03:15]Right? You must partition the array into exactly k non-MP contigious groups.

[00:03:20]Okay? So what you have to do is you have to partition that particular array given to you into k groups and the these groups should be non empty contigious groups right contigious means you should have only continuous elements you cannot take the elements from different positions and group them that is not possible.

[00:03:40]Now the score of a group is defined as so they have told you that something score will be taken score of a group will be defined as how frequency of its most frequent element. Okay. So that is the mode frequency of that group means for example if you have one subarray or a one of the groups right where you have an element something like 1 2 2 3 right something like this. So here you can see the uh one is occurring for one time, two is occurring for two times and three is occurring for one time. So what is the score of this particular group? That is the frequency of its most frequent element. Most frequent element is two and what is the frequency of two? That is two. So the score of this particular group is what? Score is two. Okay. So this is how you can find the score. This is what they have meant. Now what is your task? Your task is to find the maximum possible total mode frequency score across all K groups. Okay. So your uh what you have to do is you have to find the maximum possible total mode frequency score. Now you you because they will be giving you K as an integer and you your like what you have to do is you have to partition them into K arrays right I mean K subarrays or the K groups. So those K groups can be many right there could be many possibilities or the many combinations right now what you have to do is you have to find the maximum possible total mode frequency score. So so you need to find the maximum poss the group that is giving you the maximum possible score. Okay across all K groups. So I guess the question here is pretty understandable. Okay. Now let's move on to the input format that what input format says. So the first line contains an integer n denoting the size of the array. Okay. So first line will be integer n that will be denoting the size of an array. Second line contains integer k denoting the number of contigious groups. And each line i of n subsequent lines where z i is i will be always less than uh I mean greater than equals to zero and less than n contains integer describing a of i. Okay. So there will be like few more lines where you will be having all the numbers for that particular array. Right? Okay. So now constraints are given to you in a way that n which will be the size of array will be from 1 to 500 only. The k that will be given to you again from 1 to n only. Right? And then a of i means every element will be ranging either from like from 1 to 10^ 5. Okay? Now if you see this particular thing input this first line represents what n which is the size of an array. Second number or the second line represents the integer k which represents how many groups you have to make and the other remaining lines represents the array. Right? So if I say what is the array over here? Array is 1 2 3 1 1. Okay? So this is an array over here. So this is the input format. Okay.

[00:06:52]So see now we have seen the problem statement. We have seen the input format. We have gone through the constraints and the input everything.

[00:06:59]Right. Now let's try to understand that how we can do it. Okay. So now we know that what we will be getting and what we will be having, what we need to do and what is the final goal we need to look for. Right. So let's try to understand that how we can do it. So first of all we need to divide an array into an exactly k contigious parts. This is very important that obviously if you have such array right there could be multiple possibilities right because k is given as two. It means you have to make two contigious groups. Now the first possibility could be that you take one and then the second group will be the all the remaining elements right which is 2 2 3 1 1. Okay. Second group could be what? 1 comma 2 and then all the remaining elements that is 2 3 1 one.

[00:07:46]Right? Then third third possibility could be what? 1 comma 2 comma 2. And then the second group will be what? It will be 3 1 1 and one. Okay. And so on it will go and you will be having the last group something like 1 2 3 1 and the last group is put. Okay. So this is how you can have the multiple possibilities. So first of all what you have to do is you have to divide an array into exactly k contiguous parts.

[00:08:19]Okay. Now once you have two groups you have to go to each part and get its score. Okay. So now we know how to get the score that whatever will be the uh frequency of the most frequent element in that particular group will be taken as the score of the group. Okay. So what you will be doing is for each part you will be finding the score. So maximum frequency inside that particular part.

[00:08:42]Okay. Now once that is done when I want to know that what is the total score. So total score will be what? Score of first group plus score of second group. And what we have to do is we have to find the maximum total score. Right? So maximum total score means that which of the groupings means which of the possibilities is giving you the uh maximum total score. Okay. So what we have to do is we have to find the scores for each of the groups. Then we will find the total score for the whole possibility and then we'll move ahead and find for the other possibilities as well. Now once this is done we have to mainly focus on that we need the total score to be maximum. So we will be maximizing the total score. Okay. So this is a basic understanding that okay this is how the flow could be for the solution. Okay. Now let's quickly see that how we can write the code. So first of all this portion is just input and output thing which most probably will be given to you by infosys only. They already give you the inputs and the output lines right you just have to they also give you the function you just have to write the logic inside that function.

[00:09:51]Okay so you have n and k in both of them you are taking what integer inputs right. So n will be taken here seven and k will be taken here as two right then because you have an array so by using for loop they're taking the ar like array elements right so you will be having all the array elements that we were having over here so it's 1 2 3 and 3 * 1 okay so this is how the array will be taken now once this is done you they they only will be giving you this line that print solve n comma ka So you are passing all the three things N, K and R inside this solve function and then they will be giving you this function over here. Okay. So they will be giving you this function like this and you have to write this whole code.

[00:10:40]Okay. Now let's try to analyze the code that how we can write the exact code.

[00:10:45]Okay. So first of all what you can see over here is uh okay these are few things which we will be seeing that why we need it. Okay. So let's start with this thing which is premputee the mode frequency for every sub array. Okay.

[00:10:58]This is the major step to be done. So what I did is I created one mode u array over here. Okay. And this mode array is what um if you see this is a list having smaller sublist right and this is like how it is working. It is for i in range n. So n is what n is given to you as seven right? So you will be having seven list right and zero is the defa def default value you're taking. So this is your bigger list which you're creating.

[00:11:27]Uh let me write it like this. Now inside this what you are doing here is you're taking one zero element and that is what you are multiplying with n. Okay. And that you are create that that thing that one list one list will be what zero multiplied by n means n is seven. So you will be having a list of seven elements default value all of them will be zero.

[00:11:50]Right? So you have seven elements over here and all of them have the default values as zero. Right? So this is how it is done. Now this same thing you have to do it for for i in range n means if n is seven you have to do the same thing means seven sublists will be created for seven times. Okay. So this is what it means. Let me quickly make one. So 1 2 uh let's quickly add more. 2 3 4 5 6 7. Then you have 1 2 3 4 5 6 7.

[00:12:36]Right.

[00:12:58]Okay. So this is how my final mode list looks like. Okay. So I hope uh this is clear. Now once this is done, what I have to do is I have to just find the modes for the different groups. Right.

[00:13:09]So for i in range n. So again we are starting with for i in range n and uh let's start with the different color uh for i in range n. So I is equals to 0 because range is seven. So it is going to go from 0 to 6. Right? Now what you are doing is you're creating one default dictionary named as frequency. Okay. So let's create that one as well.

[00:13:35]So what I'll be doing here is okay. So here we have this frequency dictionary and you can see here what we are doing is instead of uh uh add like creating it manually we just call the default d of n means it is going to create one default dictionary uh with integer data types okay so you will be having something like this now once it is done you are having mx variable initialized which is with zero right now for j in range i n so we will be having all the elements now.

[00:14:14]So let's have it. Now J uh okay let's start with the very first element I is equals to zero. Now if you see for every I for every new I we will be creating new frequency and new MX. Right? So here we have done this. Now let's start with J loop for the first time. Okay. Now J loop is going to start from I to N. Now because I is zero. So J is going to run from 0 to 6 ohm. Okay. Now once this is done, what we are going to do over here is we are going to update the values of frequency.

[00:14:51]Okay. So let's have the very first loop for J is equals to 0. Now for J is equals to0, what you are doing is R of J. Now what is R of J? Okay. Let's quickly write our array over here.

[00:15:07]Okay. So this is our array. J is equals to Z. It means we're talking about one.

[00:15:12]So what we are going to do is we're going to take this one right and we're going to add it in our frequency table because it is not exist existing right now. So what is going to happen? One we will be adding and because we have already used default dict of int what it what it is going to do is one as an element as a key will be added and by default if I don't add any value zero will be taken. Okay. Now because zero will be taken. So what we are doing is when we are assigning the value we are doing plus equals to one. So what is going to happen instead of zero now one will be taken. So we know that okay one is occurring for one times. Okay. Now once this is done max MX variable will be taking what maximum of MX or the frequency of current value right so MX is what? MX is 0 0 comma fre what is the frequency of current value that is of J is J is equals to 0 which is one only right one is occurring for one time so MX will be what MX will be updated with one okay now once this is done what we have to do is we have to update the mode I value also so mode I what we are going to update it with we are going to update it with X now I is what zero J is what zero it means we are going to talk about zero list and zero at element or and we are going to update it by one. Okay. Now once this is done we're going to move to the second loop of J. Now J is equals to 1. Okay. Now what is J is equals to 1 which is 2. Again because this is a new value so it will be initialized at 2, 0.

[00:16:46]Now because we are adding one so it will be having 2 1. Okay. Now again same thing we are going to take the MX value.

[00:16:53]So what is the frequency of current element? Current element frequency is one. And what is the previous value of MX? Which is one. So maximum is one only. So it will stay at one. Okay. Now mode of I J means mode of 0, 1 will be updated zero list and first element. So this will be updated by one. Okay. Now in third loop of J is equals to two. Now what we are going to do? Same thing again two second. Now second next element is what? Two. because two is already present there only value will be updated to uh two. Okay, it means two is occurring for two times. Now once this is done we have to again uh update my MX. Now previous value of MX is what?

[00:17:36]One and the current value of two is what? Two. So two is greater. So MX will be updated by two. Okay. Now once this is done we have to update our mode of J which will also become two. Okay. Now in fourth list uh sorry fourth loop j is equals to three.

[00:17:54]Now what is the la next element that is three. So three will be added with the frequency 1. Okay. Now once this is done mx again will be updated. Previous value is two. The current value frequency is what? One. So mx will stay two only. So it will be two and we will update here.

[00:18:12]Now fifth loop j is equals to 4. Again what is the value at fourth index which is one. So we will be incrementing this element to two. Now MX will be what?

[00:18:23]Previously it was two. And what is the frequency of current element? That is also two. So it will stay two. So we will update this and we will update mode also. Now sixth loop J is equals to 5.

[00:18:36]Now J is equals to 5. Again there is one. So this will be updated to three.

[00:18:40]Now once this is done what we have to do is mx is equals to uh okay now uh the previous value is two and the current value the current frequency of 1 is what three so three so three will be updated and we will update this three once this is done seventh loop j is equals to 6 you will be having mx is equals to now before that because this is one so this will be updated to four and now your mx will be updated with four and you will be having four over here. Okay. So this is what we did is we find the uh mode or you can say the maximum occurrence at one goal. Okay. So for first uh first grouping or the first uh thing we have find that okay there is four that is the maximum that we can take. Okay. Now once this is done the whole loop is completed every J is completed we are going to do what? we are going to go with the new value of I. So in the second loop I is equals to 1 will be updated. Now what we are going to do is we going to create a new frequency and new MX is going to be created. So now you know everything is going to be raised because obviously it is the data that has been taken earlier.

[00:19:55]Right? Now we will have to do same thing again. So MX will be taken great equals to zero and uh your frequency table will be updated. Okay. Now here what is going to happen? We will be having frequency new MX new. Now J is going to work how J will be working from I to last element. Right? So I is what one?

[00:20:18]So 1 to last element 1 to 6. So you will be having first loop starting from J is equals to 1. Now J is equals to 1. It means we are skipping that first element. Right? Now because we are skipping that first element. So what will be the element that will be added here with the frequency one. Right? So again mx will be taken as one. Right?

[00:20:39]Because now it is zero. The maximum frequency will be taken. So maximum of 0 and 1 is one. So one will be taken. And because one will be taken, what we are going to do is mode of J will be updated. Now I is what? One. J is what?

[00:20:54]One. So first list I mean this is the zero element. This is the first element.

[00:20:59]Right? Now first list first element will be updated with one. Okay, same way. Now I'm not going to write the whole loop but let's just calculate it manual like manually only. So what we are going to do it in next loop we will be having this two. Now this two will update your value right now because previously MX was one and now currently the frequency is two. So obviously two will be taken right now because two is taken so MX will be updated to two. So you will be having new MX which is two. Okay. And you have to update the value 1 comma 2.

[00:21:34]So first list second element which is two. Okay. Now again the next element next element is three. So three will be added in your frequency dictionary with the value one. Okay. Now out of mx 2 and the value one two is greater. So MX will stay two and this will be updated with two. Okay. Now next element is one. So one will be added with the frequency one. Same thing MX2 is greater than the frequency one. So it will stay two and this will be updated with two. Now one again next element is again one. So two will be the new frequency of a one.

[00:22:10]Again out of two and two two is maximum.

[00:22:12]Two will stay there and two will be updated over here. Then again last element is one. So three will be I mean one more will be added. So it will become three. Now because it will it has became three. So out of two and the current frequency which is three three is greater. So, MX will be updated to three and this mode will be also updated to three. Okay? Same pattern is going to happen for all the elements. Right? So now in the next loop where you will be having third loop for I is equals to 2.

[00:22:44]What you will be doing is you will be running this J from 2 to 6. Okay. Now what is okay? Let me quickly just write over here. 0 1 2 3 4 5 6. Okay. So now we are going to start with this. Now again same whole frequency table is going to be reset. Maximum is going to this MX is going to be reset. Okay. So let me quickly just erase it.

[00:23:14]Okay. So once this is cleared again you have the whole thing to start with.

[00:23:19]Start the whole thing again. Okay. Now here this time we're going to start with the second element. So second element is what? Two. So two is going to be added with the frequency one. Now because out of maximum MX0 and the frequency 1, one is greater. So one will be taken. So MX will be updated by one. Now mode of I J I is what? Two. J is what? Two. Right?

[00:23:41]So 2A 2 means second list second element. So this will be updated with one. Okay. Next element. Next element is what? Three. So three is going to be taken as frequency with one. Right? Now out of one and one, one is maximum. So MX will remain one only and this will be updated by one. Next you have one. So again you will be having one but the frequency is one only. So out of one and one maximum is one is it will be updated by one. Then you have next element as again one. So frequency will be updated to two. Out of one and two, two is maximum. MX will be updated to two and mode will be updated to. Then you have the next element also again one. So uh it will be updated by to three and out of two and three three is maximum. So three maximum will be converted to three and mode is also updated to three. Okay.

[00:24:33]So this is how you will be doing. Now same thing going to happen over here.

[00:24:37]Now this is your fourth loop. I is equals to three where J is going to run from 3 to 6. Okay. Now third element is what? Three. Right? Three is occurring for the first time and MX that we are having is again zero. Okay. So now three is occurring for one time means out of 0 and 1 one is greater. So you have to update 3, 3. Third list, third element.

[00:25:01]Right? So third element is what? This one. So this will be updated by one. Now next element is one. So one with frequency one. Again mx will remain one only. Right? So this value also be updated by one. Then it will become two.

[00:25:16]So this will also become two. So this will also be updated with two. Then this will become three. This will become three. And this will be also updated with three. Okay. Same thing for the next loop. Uh this time you will be having fifth loop for i is equals to 4 where j is going to work for 4, 6. Okay.

[00:25:37]So fourth element, fourth element is one, right? One is going to occur for one time. So that will be and mx will be zero initially. So out of 0 and one, one is greater. So one will be taken. Right?

[00:25:49]Now because one will be taken and which which value will be updated? It is fourth list. Fourth element. Right? So this is your fourth list and what is your fourth element? Fourth element is this. Right? So you will be updating this with one. Then it will be updated with two. So this will become two again and this will be two. Then this will become three because your last element is also one. So this will become three and this will also become three and this will be having three. Okay. Now once this is done you have your sixth loop.

[00:26:18]In six loop what you will be having? I is equals to 5 and J is going to run from 5 to 6. Okay. Now for five to six again what you have to do is you will be working on fifth element. Right? Uh fifth list and fifth element. So fifth list and fifth element means this one five and six. Okay. So again now what is the fifth element which is one. Okay. So you'll be having one for one time. MX will be zero and because 0 and one one is maximum. So you will be updating it with one. Now then again you have next element is one. So it will be updated to two and this will be also updated to two. So this will be two. Okay. Now once this is done we'll move to seventh loop where i is equals to 6 and j will be going to run from 6 to uh sorry my bad.

[00:27:07]This will be n. So this will always run from this to this. Okay. But we know that in Python it just runs for one less thing. Okay. So if I say that it will run from 6 to 7, it means it is going to run for one loop only that is six. Okay.

[00:27:24]So that is it. Now J is going to run for only last element which is six which will be having the frequency one only.

[00:27:31]So maximum will get updated to one only.

[00:27:33]So your last value will get updated to one. Okay. So this is how you have premp computed the mode frequency for every subarray. These are the seven subarray possibilities that you can create out of the whole thing right out of the whole array. So you have found the mode for each of them. Okay. Now once this whole thing is clear now what we have to do is we have to start dividing it in uh subarrays and we have to just maximize the total score. Okay that's it. Now only that part part is there. So this is what we are going to discuss in the second block of code where we will be using DP. Okay. So let me make some space over here.

[00:28:19]Okay. Uh let's let's quickly have some space. So basically what we are going to do over here is see what we are doing here. We are going to create one DP array. Right? Now in this DP array if you see carefully what we are what we need is we need that I and J both things right.

[00:28:37]So what we are creating is we create we are using one info variable and now if you see initially I have defined this in variable over here which is nothing but float the negative infinity in a float number right. So basically what we are taking is we are assuming that this in variable is uh negative infinity and it is in a float data type. Okay. Now once it is been it it has been taken what we are going to do is we are going to multiply it with k + 1. Now k is what? K is 2. 2 + 1 is what? Three. So we are taking it for three times. And how many possibilities are there? Seven possibilities are there. So we will be repeating it for the seven times. And that is why if you see there the i range we are taking is from range to 0 to 0a n + 1. Right? So that is what we are going to take. Okay. So let's quickly have it over here.

[00:29:41]Okay. Let's try it here. So what how my DB array will look like? It will be having a larger range. Right. So first of all because K is equals to two. So K + 1 means three. It means in each uh sub list we're going to have three elements and each sub list what we are going to take is we're going to take this infinity variable. Okay. So this is your first then this same thing the same list you're creating it for how many times for i in range n + 1 so n is what n is 7 n + 1 means 8. It means seven times you have to create it right from zero uh I mean from 0 to 7 right? So this is for zero uh range then you will be having okay let me just quickly write it like this second sublist Okay. So this is a zero, first, second, third, fourth, fifth, sixth and seventh.

[00:31:16]Okay. So this is uh like from this loop is going to run from 0 to 7. So that is why for each loop we have this particular list where there will be three elements and all of them by default will have the value in and inf is a float of negative infinity.

[00:31:34]Okay. Now once this is done we have to initialize dp of 0 as 0 because we know that initially this is going to be nothing. Okay. Now let me explain you that what this I because you see uh we can define this whole DP array as in DP of IG right. So what this I is going to take I is going to have all the modes like what is the maximum mode you're getting right and at which position. So what you are having is for i in range 1 comma n + 1. Okay. So you are starting with the first i which is starting from 1 to n + 1 which is 8. Okay. So you will be having first loop from 1. Okay. Now once this is done for groups in range 1 comma k + 1. Now inside this what you're having is you're having k loop running from or you can say groups loop running from 1 k + 1. Now 1 comma k + 1 means 1a 3. So it is going to start from 1. Okay. Now how we are doing is for previous in range i. Okay. Now here we have another loop previous which is in range i. So it means from zero to i. So 0 to 1 because i right now we have is one. So we are going to run it for only f one time for the first loop and then it is going to uh increase automatically. So let's have our first loop where I is going to start with one.

[00:33:07]Groups is going to start with one and previous will be starting from zero and it will go up till one. Okay. So DP of I, groups is equals to maximum of these three values uh I mean these two values.

[00:33:20]Okay. So let's have it over here. DP of I which is one groups which is 1 is equals to what you have to do is maximum of two values first what is currently that we are having so at 1 comma 1 we are having negative infinity right so we will be taking negative infinity comma DP of previous groups minus one so previous is what zero it means we're taking DP of 0 comma groups is what 1 1 - 1 is also zero Okay. Plus mode of previous which is previous is what? 0 and I - 1. I - 1 is also zero. Okay. Now if you try to see DP of 0 comma 0 is what in 0 only and mode of 0 comma 0 is what? It is one. Right? Now 0 + 1 0 + 1 will make it 1. Now out of minus infinity to one I mean out of minus infinity and one which one is greater?

[00:34:21]One is greater. Now because one is greater so dp of 1 comma 1 will be sorry dp of 1 comma 1 will be updated with what will be updated by one. Okay. So this is how in the same way we have to calculate for each of the elements.

[00:34:37]Okay. Now same way now previous is going to not run for any other element because it it is going to work from uh in range I and I is what? one in this case right now. So 0 comma 1 and it is going to run only for one loop that is previous equals to 0. Now once this is done this groups is going to be uh go on the next loop because this was the first loop for groups. So second loop of groups will be what?

[00:35:03]For two, right? And now what we are going to do is again same we going to call this previous loop and previous is going to run from again in range I only.

[00:35:13]So it is going to run from 0 to 1 and which is only one loop which is previous of zero. Okay. Now again what we are going to calculate? We are going to calculate DP of I which is one and groups which is two. Okay. So now we are going to calculate 1 comma 2 which is this particular element. Okay. Now what it is now if I try to find the same thing uh again we have to take the maximum of two elements the current stored ones right. So the currently one is negative infinity only right and what is the previous one? So previous DP of previous previous is what? 0 and groups is what? Uh sorry, groups minus one is what? 1. Okay. Plus DP of now what is uh mode of previous? Pre previous is what? Previous is 0 and I minus 1 which is also zero.

[00:36:18]Okay. So now if you see dp of 0a 1 dp of 0a 1 is what? negative infinity negative infinity in infinity plus mode of 0 which is 1. Okay. So it will be negative infinity. So what is going to happen? It will stay negative infinity because if I add anything like in negative infinity if I'll try to add uh any value which is uh uh like if I try to add one over here it will stay as it is right there will be no as such changes. So it will be negative infinity only. Now once this is done, same thing we are going to do for uh uh do for the same thing again and again and once the whole thing is done what we will be getting is we will be getting that for each group if I am taking the previous elements how they are going to be summed up and how we are going to get the final result. Okay. So this is the final uh final thing that will be happening in this whole loop.

[00:37:18]Okay. Now let's try to run a next loop. Let me change the color over here.

[00:37:30]Okay. So now we have the uh next loop for groups. Okay. Because groups is going to run from 1 to two. Okay. Groups is also done. Now we have to run the next loop for I. I is equals to 2 because 1 comma 8 is uh the main range.

[00:37:48]So first loop is already done. Now we are going to start with the second loop.

[00:37:52]Now in second loop what we are going to do is same first loop of group. So this is going to run from 1 comma k + 1. So again 1a 3 right. So it is going to run for two times. Right? which is uh first loop will be groups for groups for one and the second loop will be groups for two. Okay. Now in groups of one first thing will be first loop of previous.

[00:38:27]Now previous is going to range from 0 to two uh because I is what? Two. So previous is going to run for zero and previous is going to run for one. Right?

[00:38:39]Now in each loop what we are going to update is we're going to update DP of 2 1. Okay. Now DP of 21 will be what? It will be taken maximum of the current value of that particular list. So 2 of one means negative infinity.

[00:38:57]Right? Comma what is the next value? DP of previous groups minus one. So DP of previous previous is what? Previous is 0 groups is what? 1 1 - 1 is 0 means DP of 0 comma 0. DP of 0 comma 0 is what? 0.

[00:39:11]So 0 plus mode of now mode of previous I - 1. Mode of previous means 0 and I - 1 means 1. So mode of 0a 1. So mode of 0a 1 is what? It's one. Right? So it will be updated by this. So now out of negative infinity and one because this is going to be one only. So out of negative infinity and one what you are going to get is one only. So maximum is one. It means this particular value which is dp of 2 comma one will be updated with one. Okay. Now same thing is going to happen for previous of one.

[00:39:49]We are going to take okay let me write it over here. We're going to take it like this. DP of I groups. So group I is what? I is two groups is what? Uh groups is also one.

[00:40:05]Okay. So this is the value that we are going to uh update. Now how it is going to be updated with? It is going to be updated with maximum of current value.

[00:40:15]So maximum of current value current value is what? One comma the uh same values DP of previous groups minus one.

[00:40:24]Previous is now one groups minus one is again zero. So 1 comma 0. So dp of 1 comma 0 means dp of 1 comma 0 is this one which is updated to 1. So 1 + now mode of previous comma i - 1. Mode of previous previous is 1. I - 1 is also 1.

[00:40:41]So mode of 1a 1. Mode of 1a 1 is what?

[00:40:44]1. So 1 + 1 is 2. So this is going to be two. Now out of 1 and two which is greater 2 is greater. So this value which we have updated to one will be now updated to two.

[00:40:58]Okay. Now once this is done, what we have to do is the next is uh groups of two which will be the next second loop for groups. Now same thing is going to happen here as well. Here again two loops is going to work for previous is equals to 0 and previous equals to 1. Okay. Now same thing previous equals to 0 for previous equals to 0 we going to find the value of DP of I which is 2 and 2. Okay. Now DP of 2 comma 2 means we are talking about this particular element. It will be what? It will be maximum of it will be maximum of what?

[00:41:35]It will be maximum of two values. DP of previous groups minus one. So previous is zero groups minus one which is 1 0a 1. 0a 1 is what? 0a 1 is infinity.

[00:41:47]Right? So negative infinity negative infinity uh let me just write it over here. Maximum of negative negative infinity comma. Now what is the next element? D uh sorry okay let me just write it over hereative infinity plus now whatever will be the value right mode of previous I minus one. So previous is what? 0 and I minus one is what one right? So 0 comma 1 0 comma 1 is what? This particular element. So which is sorry this particular element right? So which is one only. So negative infinity + 1 will make it negative infinity only. Right?

[00:42:28]So there will be no as such change. So it will stay negative infinity for now.

[00:42:33]Now in second loop in second loop of previous is equals to 1. Again same element will be updated. DP of 22 in a way that maximum of two values will be taken. DP of I comma groups. Now I comma groups means same 2a 2 which is negative infinity right now. Comma DP of previous groups minus one. Now previous is one groups minus one is what? One. So 1 and 1 and 1 is what? One. So 1 comma sorry 1 + more uh okay 1 comma 1 1 comma 1 means this particular element right this particular element is negative infinity only. So it will be negative infinity comma and then mode of previous comma i minus one. So previous is what? Previous is again 1 and i is what? I is 2. So 1 comma 1 it means we are talking about this particular element. So again if you see negative infinity + 1 will make it negative infinity only and out of the two two elements the maximum will stay negative infinity. Right? So there will be no change in uh here that is 2. Okay.

[00:43:39]So it will remain as it is. Now same pattern is going to be followed for the third group, fourth group, fifth group, sixth group and seventh group. Okay. So now let's try to analyze that what we are getting from the whole thing that we are doing here. Okay. So let's quickly change the color over here of so right now if as I already told you how the group groupings are going to become. So in the first group what you will be having is you will be having one in first group right and the second group will be what 2 uh 3 1 one right now if you try to analyze what is the frequent what is the score of this particular group which is one and what is the score of this particular group because the ma most frequent element is one and it is occurring for three times so three. So 1 + 3 is what? It is equals to 4. Right?

[00:44:34]Now in second group what it will be? It will be uh the grouping will be something like 1a 2 and in the next group you will be having 2a 3a 1a 1 comma 1. Okay. Now what you are going to happen out of this one is the final answer final score and out of this again three is the final. So the final score will be what? 1 + 3 which is uh four.

[00:44:58]Okay. Now next uh next group will be what? Next group will be 1a 2a 2 and the another group will be 3a 1 comma 1. Okay. Now from this particular group the score is two because two is occurring the most frequency most frequent time which is for two times.

[00:45:18]Right. And here one is occurring for three times. So three will be the final answer. 2 + 3 is what? Five. So the maximum number till now what we're getting here is five. Means the maximum score that we are getting here is five.

[00:45:30]Okay. Now same way the next group will be what the another group that can exist which is 1a 2 comma 3. Right. And another group is what? 3 * 1.

[00:45:44]Now again here the score is two and here the score is 3. 2 + 3 is again five. Right? So the maximum score till now we are getting is five only. Now next element is what uh I mean the next possibility of the grouping is what that you have 1a 2a 2 comma 3 comma 1 right 2 * 2 and there will be 2 * 1 remaining here. Now again out of the whole thing you can see two is occurring the two and one are occurring for the most frequent time and it is for two times only. So two will be taken and here also two is taken because two is the latest. So 2 + 2 is what? Four. So because four is lesser than five. So again we will be storing that five only.

[00:46:29]That is the final answer. Now once this is done what we will be getting is we will be uh having another grouping which is 1 2 2 3 1 1 right and next group is one. So here again one is occurring for three times and here one is occurring for one time. So 3 + 1 is four. So this is the final group that we can create.

[00:46:51]So out of the all out of all the groups the final uh the final answer that we're getting means the first group where we getting the maximum output will be returned. Okay. So if you see what we are returning here is we are returning DP of NK. DP of NK means the value the group that is giving you the maximum value will be returned in the end. Okay.

[00:47:14]So this is the whole scenario. This is how it is going to work. uh like uh I guess uh this is clear you have to just understand the question you have to see that how it can be done and then you have to just apply break it in two parts first will be the premputing the mode frequencies for each element of every subarray right and the second will be the portion where we will be actually dividing them into subarrays and we will be calculating that what would be the maximum frequency we can get for each grouping okay so this is how this question can be done. So I hope this particular question is clear and let's move on to the next uh question which is frequency balanced window. Okay. Now in this problem what we are having is in satellite signal. Okay. The question says in satellite signaling processing uh upstream of n data packets is received. Okay. So there is one satellite which is sending some number of packets which we can say that there are n data packets that are being received. Okay. And each packet is classified into a category which is a fi. So there is two things that they are that particular packet is having. One is the category and the second that carries a specific signal weight which is wi. So you have two arrays.

[00:48:36]One is kind of a category array. Okay, which will be showing the category of that particular packet and the second will be the weight array which will be showing the weight of that particular packet. Okay, so you will be having a category ranging from 0 to C1. Okay, something like that and you will be having the weights representing its data density. Okay.

[00:49:00]Now a monitoring window L comm R which is a contiguous range of packets from index L to R is considered frequency balanced.

[00:49:12]Okay. So what you are having is you will be having one monitoring window. Okay.

[00:49:17]So you can assume that we have that window now. So that window is there where you will be having the contigious elements only because they are saying contigious range packets from index L to R. Okay. So some index L to R there will be that contigious range of packets that will be taken in that particular window.

[00:49:39]Okay. And this window is considered frequency balanced.

[00:49:44]Okay. So this fre uh this particular window will only be considered frequency balance if there exists at least one category that appears strictly more than half of the packets in that window.

[00:49:58]Okay. So what you will be having is uh okay let's first try to analyze this.

[00:50:04]there is one satellite okay which are sending some n number of packets and in these n number of packets let's let's assume n is given as four okay so there are four sec four packets sent by a satellite okay this is 0 1 2 and three now once this is done what we are having is we are having two things attached with each of the packets so the first is the category some kind of category of that packet and some kind of a weight which shows shows the data density of that particular pattern. Okay. So let's assume this is 1 2 3 1 4 2 8 4. Okay.

[00:50:44]Something like this. So what what does this data means? This means that zero packet the zeroth packet is of category 1 and has the weight four. Okay. First packet has the category two and has the weight two. Then second packet is of category three and has the weight two.

[00:51:05]Third packet is a is is of category 1 and has the weight four. Okay. This is how the question is. Now what you have to do is you have to create one window from index L tor. Okay. And they have already told you that this window will be contig of contigious strings. Right?

[00:51:24]So whatever the subar you will be considering that window is what sub area only. So whatever the sub area you will be considering should be contigious and this particular window will become frequency balanced. We can call it frequency balanced only when at least one category. So you it means the window that you're creating is for category array. Okay. Okay. So the window that you're creating, okay, whatever the window you will be creating will be from the category means you will be creating a subarray from this category array.

[00:51:59]Okay. Now this particular window will be called frequency balance if there exist at least one category that appears strictly more than half of the packets in the window. So whatever the number of packets you're taking in your window, for example, you're taking the number of packets in your window as four, right?

[00:52:16]So what you have to do is if if that particular window has the number of category you have to find the category which is occurring for more than half the times of the window size. So half the time of the window size for example the window size is four. So half the size is what? Half the size means two means any category if there is any category in this particular window which is occurring for exactly more than two times then this window will be known as frequency ballast. Okay, I hope a bit of it is clear when we will be seeing the inputs and everything we will be getting it better. Now in another words or in other words some category is a strict majority in window. Okay, some kind of thing is given to you where uh some category means the category numbers that you will be having is a strict majority in window. Okay. So strict majority means what? That it is occurring for uh more than the half of the size of the window. Okay. So whatever is your size of the window if you divide it by two and whatever the number you're getting if any of the categories occurring for that number of times or more than that it means that particular window is known as frequency balanced. Okay. Now what your task is? Your task is to find the maximum total weight. Okay. Okay. So you have to find the maximum total weight among all the possible frequency balanced windows. And the total weight of the window is this. Okay. So uh how you will be finding the total weight of the window means adding all the elements from L2R in your weight cells. Right? So whatever is your L2R you have to add all the elements all the weights of that particular element and that will be your total weight of the window. And what you have to do is you have to find the maximum total weight among all the possible frequency balanced windows. So the very first important the very important thing you have to do is what first of all you have to find that what all windows are frequency balanced.

[00:54:17]Okay. So very important thing is that you find all the frequency balanced window. Now once you have all your frequ frequency balance windows you have to find the total weight for all of them and then in the end you have to find that which one is which one out of them is having the maximum total weight. So that is what you have to return. Okay.

[00:54:41]Now let's try to understand what the input format says. So the first line contains integer n which represents the total number of packets. In second line the it contains integer C denoting the total number of possible categories.

[00:54:55]Okay. So they are giving you some possible number of categories that is present. Okay. The next n line contains integers a of i which is representing packet categories and then you have w of i which represent packet weights.

[00:55:11]Okay. And these are the constants given to you. Now let's see the input over here. So you see this seven. Seven is what? Seven is n which is the number of packets. It means seven packets are sent by the satellites. Three is your possible categories. Total number of possible categories. Okay. Then this uh seven times 1 2 3 4 5 6 7. Okay. Till this much I guess. So a of i is what here?

[00:55:40]Okay. A array is what? A array is 1 comma 1 comma 2 1 0 1 and 1. Okay, because seven elements because seven packets it means seven categories it means seven weights right. So whatever you will be having you have to just take it for seven times. Now all the remaining ones right till this this is this and all this are the weights. So 4 2 3 5 1 6 and 2. This is your weight.

[00:56:13]Okay. So if you see what does this mean?

[00:56:15]This means zero packet. Okay. If we talk about zero packet, if we talk about zero packet, what is the category of that packet which is one and what is the weight of that packet which is four.

[00:56:27]Okay. For first packet the category is one but the weight is two. For second packet the category is two the weight is three. For the third packet category is one the weight is five. Fourth cate fourth fourth packet has the category zero and has weight one. Fifth packet has category one and weight six. And then sixth category has packet uh sixth packet has category one and weight as two. Okay. So this is what it means. Now what we have to do is from this categories uh window the category array we have to create the windows okay and we have to find that which one out of those windows is a frequency balanced windows okay so the first thing what we have to do is a window is valid we understood that a window is valid only when frequency of some category is greater than the window size divided by 2. So for example if you are considering the window as 1 comma 1 comma 2 comma 1. So what is going to happen here category 1 appears three times right this category 1 is appearing for three times and the window size is what window size is four currently four divided by two is two and the maximum appearance which is three times is greater than the window size. It means this particular window is a valid window. Okay. So this is how we need to find the valid windows. Now once this is done for a category X for any category X to become majority count of X should be greater than the remaining elements.

[00:58:00]Okay. So if I'm talking about this particular window, right? And if I want to find if uh what is the majority element here, right? So what how do we need to do is we need to find the count of X. So for example, if I take one, so count of one is what? Three. Three should be greater than remaining elements. Now remaining elements are how many remaining elements is one. So three is greater than one. It means we can say that one is a majority majority element.

[00:58:27]Okay. So this is how it is given. Now next is we can okay. Now these are the approaches that we are starting with that we can transform the array. We can make it + one if ai is equals to equals to x and we can make it negative one if it is any other value. Okay. So what we are doing here is once we know that which one is the majority element in the whole category thing then what we can do is we can simply say that okay if your array is that particular majority element we will take it as plus one and for the other remaining elements we will take it as negative one just to differentiate that which one is the majority element and which one are not.

[00:59:06]Okay, then a subarray has majority x if and only if sum of total okay sum of transformed subarray is greater than zero. So this is something we will be understanding when we will be doing question and now the problem becomes what basically we are trying to solve the whole problem.

[00:59:27]First of all we we are breaking into sub problems and then we are solving the small small portions and then we are coming bringing all them together.

[00:59:35]Right? So find the in the end what we will be doing is find the maximum weighted subarray whose transformed sum is possible. Okay. So this is a final uh question that we will be mainly focusing on. Okay. Now what is the optimal approach for every category? What we will do is we'll convert an array into plus one for current category and negative one for others. Okay. We will be using prefix sums and then we will maintain the minimum prefix sum seen so far. Okay. Now once it is done we will maximize the weight window sum where my current prefix will be greater than pre previous.

[01:00:13]Okay. This converts the problem into a small into a smart prefix optimization problem. Okay. So this is how the final approach will look like. So here again same you can see there are all the inputs we have given with right and we have given with the output line as well.

[01:00:31]Here is my function name and here we need to write the whole logic. Okay. So let's quickly start with it. So the very first thing is we need the prefix array, right? Prefix some array. So we are taking one prefix weight array over here which is we are initializing all the values with zero for n + one times. Okay let's quickly also write all the values.

[01:00:53]So n was given as seven over here. Yes, n was given as seven. C we are taking C it as three right and A and W we need to write again so it's 1 1 2 1 okay A is what 1 1 2 1 0 1 1 right 0 1 and what is uh weight list or maybe okay weight list is what? 42 351 162 4 2 3 5 1 6 2 Okay. So these are all the input values. Now prefix weight because n is seven. So prefix weight is going from uh is multiplying we are multiplying it with n + 1 means eight things right? So we have to add eight elements over here and all of them we will be having the default value as zero. Right? Now once this is done we have to find the u okay initially we are taking answer as zero. So let me just initialize it also. Okay. So what we are doing is first of all we are finding the prefix sum for weights. So prefix weight we have created. Now we have to simply range in uh that particular array.

[01:02:22]Right. So for i in range so first loop i is equals to uh 0 and it is going to run from 0 to 7. So 0 to 7 means 0 to 6 it is going to work. Okay.

[01:02:33]So prefix of weight of i + 1. So prefix weight of i + 1 i is zero. It means we're going to talk about fifth for the first element. Okay. Now this will be what? This will be prefix weight of previous value which is zero plus the weight of that scenario. Right. So if you see the pre previous weight was zero in prefix weight right and the weight of zero element is what four. So 0 + 4 will be four. So this will be four. Okay. Now in second loop I is equals to 1. What is going to happen? We are going to find for this particular element that is I + 1 which is second element. And it will be what? The prefix weight of previous value plus weight of I. Right? So prefix weight of previous value is what? Four.

[01:03:19]4 + the value at 1. So 4 + 1 2 is 6. So 6 will be taken. Now in second loop this will be what? 6 + 3 which is 9. So 9 will be taken. Then for this particular loop it will be 9 + next value that is five. So 9 + 5 is what? Uh 14. Right? So 14 will be taken. Then 14 + 1 which is five. Uh 15 right? So that will be taken. 15 + 6 will be 21 and 21 + 2 will be 23. Okay. So this is my prefix weight that I have found. Okay. Now once this is done, what we have to do is now because we need the unique categories.

[01:04:01]Categories is something the same. Now if I'm saying that this particular person is coming in category one and this particular person is also coming in category one. Category is something which need should be if it is uh like unique then it is good right so what we're doing is in in category for categories we are creating one set so take we can take the uh unique ones right so what we are doing going to do here is let me erase the extra lines so that we can have space for later on.

[01:04:37]So what we are doing here is we're creating one category set and this is what how we are doing is we know that from basically we'll take this whole A and we are going to convert it into set means all the like unique values will be taken here right so all the unique values are 1 2 0 right so let me just write it as 0 1 and two these are the uh this is the set that we will be getting okay now what we have to do is we have to try every category as majority Now we will try to assume that okay maybe zero can be a majority maybe one can be a majority or maybe two can be a majority right so for target in categories so we are going to start looping inside this categories so in first loop my target will be what zero okay so we are assuming that prefix is zero okay now what we are doing here is minimum prefix seen so far we are going to find okay so prefix initially we have initialized as zero that okay we know that prefix right now is zero and we just need to find the minimum prefix seen so far. So minimum prefix also initialized with zero and minimum index we have initialized with zero. Okay. Now for i in range n. Now for i in range n because we have to traverse accordingly. Right? So I in range n means i is going to initialize with zero but it is going to range from 0, 7. Okay. Now what we are doing is we are going to create one transform array.

[01:06:04]So if a of i is equals to equals to target we are going to do prefix plus equals to 1 else we are going to update it with okay so this is what we are going to do now how okay let's let's have it so if a of i is equals to equals to 1 i is what zero I a of 0 is what a of 0 is 1 so is it equals to equals to target no target is zero right target is zero so it means one is not equals to zero what we are going to do is we are going to go over here and we will be subtracting one from prefix. So my prefix will become -1. Now once my prefix has become negative 1, I'll go to this thing. Majority condition satisfied or not? So if my prefix is greater than minimum prefix now minimum prefix is what? Minimum prefix is zero. Right? Is my current prefix which is neative1. Is it greater than negative prefix? If it is greater than negative prefix it means the element that I'm selecting is a majority element and if it is not it means it is not. So right now if you see the condition is false. So we will directly go over here and what we will do is update the minimum prefix. So if prefix is less than minimum prefix which is current case what we are going to do minimum prefix will now become what? I'm writing it as MP. minimum prefix will become the current prefix which is negative 1 and minimum index will be added by I mean added by one because we have initialized it okay so it will be what I + 1 I is what 0 + 1 is 1 okay so this is how we are done now once this is done again we'll move to the second loop of I okay so this was my first loop this was now we have to move to the second loop of I is equals to 1 now again same thing If a of 1. A of 1 is what? One. Is it equals to equals to target? Target is zero. No, it is not. Now because this is not. So what we have to do is again um again what we have to do is again we'll go over here and prefix minus equals to 1. Now prefix is already -1. We have to again reduce one from it. So it will become -2. Okay. Now once it has become -2 again we will be checking the same thing. If prefix is greater than minimum prefix. So prefix is right now -2 and minimum prefix is neative -1. So the condition is false. So we'll go over here. Is my prefix less than minimum prefix? Yes, it is. Now because this is true, what we are going to do is my minimum prefix will become -2 and my minimum index will move to i + 1.

[01:08:40]So I is 1. 1 + 1 is okay.

[01:08:45]This is how we need to do. Now we'll move to the third loop. In third loop again what we have to do here is okay in third loop I is equals to 2. Now same thing is my current I mean the value at index two is what? Two. Is it equals to equals to target? No it is not. Because it is not so my prefix will be what? Will be decreased by one. So it will become -3. Now again same thing we will directly go over here because my prefix is less than minimum prefix. So what will happen? My minimum prefix will update to -3 and my minimum index will become three. Now fourth loop I will be three. Now I is three. The argument at index 3 is 1. 1 not equals to zero.

[01:09:36]Again same thing my prefix uh will become uh like will subtract one from it. So it will become -4. And now my minimum prefix because minimum prefix is greater than prefix or you can say prefix is less than minimum prefix. So we have to update my minimum prefix which will be minus4 and my minimum index will become I + 1 which is four. Okay. Now in fifth loop I is equals to uh four. Right? Now fourth value is what? Fourth value is zero. And now zero is equals to zero because target is also what we have taken zero right. So now because element and target both of them are equal. So we are going to add one in my prefix. So now my prefix will become -3. Okay. Now I have to check is my prefix greater than minimum prefix. Now minimum prefix is what? -4. And my prefix is what? -3.

[01:10:34]So yes -3 is greater than -4. The condition is true. Now because the condition is true it means right now where I am is a majority element. Okay.

[01:10:44]So what we have to do is we have to find the total weight. So total weight is equals to now see how we are taking the total weight. So prefix weight of I + 1 minus prefix weight of minimum index. Now prefix weight of I + 1 I is what? Four.

[01:11:02]4 + 1 is five. Let me quickly just write it over here. 0 1 2 3 4 5 6 7. So at fifth index what we are having is 15. So 15 minus prefix weight of minimum index.

[01:11:18]Now minimum index is what? Four. Prefix weight of four means this one which is 14. So total weight for now is what?

[01:11:28]One. Total weight for now is what? One.

[01:11:32]Okay. Now once this is done, answer will be what? answer will be taken the maximum of current answer or the total weight. So because answer currently is zero and the total weight that we are getting is one. So one will be taken.

[01:11:44]Okay. Now once this is done again we will check the same condition. Next condition is my prefix is less than minimum prefix. So prefix is -3 minimum prefix is4. The condition is false. It means no change needs to be done. Okay.

[01:11:58]Now once this is done again we'll move to the next loop that is six loop. I is equals to 7.

[01:12:04]Now for i= to 5 what do we have is the new element is 1. Is my 1= to target? No it is not. So same thing -3 will become -4.

[01:12:15]Right? Now what we will do is we'll come over here. Is my prefix greater than minimum prefix? So is my prefix which is -4 greater than negative prefix? No.

[01:12:25]Right? Then we'll come over here. Is my prefix less than minimum prefix? No, it is not. It means both the conditions are false. Now because both the conditions are false nothing is going to happen and we'll move to the seventh and the final loop which is i= to 6.

[01:12:40]Okay. Now for i is equals to 6 the value is again 1. Is my 1 equals to zero? No it is not. So again my prefix will become -1. So it will be -5. Now is my prefix greater than minimum prefix? No it is not. Is my prefix less than minimum prefix? Yes it is. So -5 is less than -4. So this condition is true and because this condition is true my minimum prefix will be updated by -5 and my minimum index will be updated by 6 + 1 which is 7.

[01:13:12]Okay. Now once the whole thing is done if you see the whole for loop is completed. Now once the whole for loop is completed now what we are going to do we are going to do the same thing for a new target. Okay in this particular loop we we we assumed target to be zero.

[01:13:30]Right? Now in second loop what we will assume? We will assume the target is what? Target is one. Because the next element in categories is what? One.

[01:13:40]Okay. So now what we will be doing is we will be doing the same thing for but we will be searching for the element that is one. The categories that are belonging to one. Okay. So we will be having first loop i is equals to0. Let's quickly have it. So in this what we what do we have here is uh so obviously again everything will be restarted you will be having new prefix right prefix is zero minimum index is zero and minimum prefix is also zero you have everything new okay so now what you have to do is again same thing I is at zero you have to go to the zeroth element zero element is one is equals to 1 which is target right now because this is same I mean the uh element is actually the target only. So we have to add one in my prefix. So because prefix is zero so now it will become what? 0 + 1 which is one right.

[01:14:34]So it will become what?

[01:14:37]It will become one.

[01:14:45]This will become one. Okay. Now because this became one what we have to do is when we'll check is my prefix greater than minimum prefix. Yes. prefix is one and minimum prefix is zero. So what I have to do is I have to find the total weight. Now total weight is equals to what? Prefix of prefix weight of I + 1.

[01:15:02]I is what? 0. So I + 1 means this. So this is four minus prefix weight of minimum index. Minimum index is what? 0.

[01:15:11]So 4 minus 0 is four. So total will weight will be taken as four.

[01:15:18]Now answer will be what? If you remember in previous loop we got the answer as one over here right we got the answer we got the answer as one over here now it is already one right because we can't update it again and again answer once taken will be there right you have to just update it update it in each loop because we need to find the maximum total weight right so because it is one earlier and now we're getting total weight as four so four is maximum so answer will be updated to four okay Now in second loop I is equals to 1. Again because the value is what? At index one the value is one only. So my prefix value my prefix value will be added by one. So if I add one in my prefix what it will become? It will become two. Okay. Is my prefix greater than minimum prefix? Yes it is greater. So again we have to find the total weight. Now total weight will be what? Again prefix weight of I + 1.

[01:16:16]So I is 1 and 1 + 1 is 2. So prefix weight is 6 minus the previous one right I mean the minimum index value. So minimum index is zero. So the value at index zero. So which is six is the final total weight. Now because we have to update our answer because the previous value is four and the current total weight we are getting is six. So answer will be updated to six. Now third loop i is equals to 2. For i is equals to 2. If you see uh the value is two right which is not equals to target. Now because it is not equals to target we have to reduce one from the prefix so it will become one. Now uh is my prefix still greater than minimum prefix. The condition is true. Now because the condition is true again we have to find the total weight. Now total weight is what? Prefix of two. Prefix of two is what? Six. So six uh sorry prefix of three. Prefix of three. Three is what?

[01:17:12]9. 9 minus prefix of minimum index.

[01:17:15]Minimum index is still zero. So it will be zero. So which is 9. Okay. So my answer will be what? Answer will be also 9. Okay. Now once this is done, we have to move to the fourth loop. In fourth loop, I is what? I value will be three.

[01:17:34]Means we have to find for the third element. Now what is the third element?

[01:17:38]Third element is one. Right? So again we have to add one in my prefix which is two. Okay. Now once this is done again what we have to do is we have to uh like uh because prefix is greater than minimum prefix. Right? So again we have to find the total weight. Now total weight is equals to prefix weight of four. So prefix weight of four is what?

[01:17:59]14. 14 minus prefix weight of minimum index. Minimum index is still zero.

[01:18:05]So 14 minus 0 is 14. So final answer is 14. So answer will be updated to what?

[01:18:10]Answer will be updated to 14. Now in the next loop answer uh we have fifth loop.

[01:18:17]In fifth loop what we have is zero.

[01:18:19]Right? Now because we have Z okay let me just write it like I is equals to four.

[01:18:23]Now because we have zero which is not equals to target. So prefix will be uh like we have to subtract one from prefix. Right? So once we have subtracted one value from prefix it has became one. Is my prefix still greater than minimum prefix? that is true. Now because that is true, what we have to do is we have to um uh find the total value. So total weight is equals to what? Prefix of I + 1. I is 4. It means I + 1 means 15 minus prefix weight of minimum index. Minimum index is still zero. So it will be 50. So now my answer will be updated to 50.

[01:19:05]Okay. Now once this is done what we have to do is we have to move to sixth loop.

[01:19:09]So let me write it over here. So in sixth loop I will be five right in I is equals to 5 what we have to do is again fifth element is what? Fifth element is one. Now fifth element is one means we have to add one in it. So prefix sum will become two. Again because two is greater than um I mean the prefix sum is greater than minimum prefix. So again we have to find the total weight total weight of um okay so total weight will be where okay let me just write it over here yes total weight is equals to uh 21 right 21 minus 0 which is 21 so answer will be what answer will be 21 okay now in seventh loop what we have to do is uh in seventh loop we have to again move ahead and I will be six now sixth element is also one and prefix sum is uh prefix is two. 2 + 1 will also become three. Right? So now what we have to do is again we'll check is my prefix greater than minimum prefix obviously.

[01:20:12]Right? So we have to again find the total weight. Now total weight is what?

[01:20:16]23 minus 0. So total weight is what?

[01:20:20]Total weight is 23. And thus my final answer will be what? Final answer is 23.

[01:20:28]Sorry not final answer. I mean the answer that we're getting here is till now is 23. Okay. Now prefix is less than minimum prefix. No it is not. So nothing is going to happen. But if you see all the loops are done. Now because all the loops are done we'll again go back to this particular line which is target in categories. So what is the last element that we are having in categories? That is two. Okay. Now the same thing is going to work but for element two. So now this is your final third loop where your target will be what? Two. Okay. And you will be like uh doing all the loops again for target is equals to two. Now for i is equals to0 again you will be having what? You will be having prefix as zero. You will be having minimum prefix as zero and you will be having minimum index as zero.

[01:21:20]Okay. Now once this is done I is equals to 0. You have to start with. Okay. So again the first element is one. One is not equals to target prefix. So what you will be doing is negative -1 with this.

[01:21:31]Okay. Now is my prefix greater than minimum prefix? No it is not. Is my prefix less than minimum prefix? Yes it is. So what you will do? You will update your minimum prefix with the value prefix which is -1. And you will update your minimum index as I + 1 which is 1. Okay. Now second loop I is equals to 1. Now for i is equals to 1 is my value matching with target? No, it is not. So again you'll be subtracting one from prefix. So it will become -2. Right? Now again is my prefix less than minimum prefix. Yes, it is. So what you have to do is you have to again update your minimum prefix to -2 and you have to update minimum index to two. Now in third loop you have i is equals to two. Now i is equals to two. You have the value as two only and the target also is two. It means this time you will be adding one in your prefix. So now you will be having negative 1 as your answer. I mean for the prefix right now is your prefix greater than minimum prefix. Yes, the condition is true because -1 is greater than -2. So what you will be doing is you will be calculating your total weight. So total weight is what? To prefix weight of uh three prefix weight of three is what? 9 9us prefix weight of minimum index. Minimum index is what? Two. Minimum index is uh of 2 is 6. So 9 - 6 is 3. Now because we have to take the maximum value for the answer. So because it is already 23 and now we are getting it as three. So obviously 23 will remain as it is.

[01:23:09]Right? So the final like the answer still is 23. Now once this is done is my prefix less than minimum prefix no obviously not right. So what we'll do is we'll move to fourth loop where i is equals to three. Okay. Now at third index you have your value as one because it is not equals to target. So you will be reducing one from your prefix. So it will become -2. Okay. Now once it has beame -2 again is your prefix less than greater than minimum prefix. Now minimum prefix is also -2 and prefix that we are currently having is also -2. So both the conditions are going to fail and because both the conditions are failing nothing is going to happen and we can directly move to the fifth loop which is i is equals to 4. Okay. Now once this is done what you have to do is same fourth element fourth element is 0. 0 is not equals to 2. You will be subtracting one from your prefix sum.

[01:24:06]So it will make it -3. Now once -3 prefix is -3 minimum prefix is -2. So obviously next the second condition will be true that prefix is less than minimum prefix and then what you'll do is you'll update your minimum prefix as -3 and you'll update your minimum index as uh five. Right? Now once this is done what you have to do is uh moving to the next loop which is i is equals to 5.

[01:24:32]Now for i is equals to 5 fifth element is what? 1 is equals to 2. No it is not.

[01:24:37]So what you have to do is you have to again subtract one from your prefix. So it will make it -4. Now is your -4 less than the minimum prefix that is -3? Yes, the current value I mean the condition is true. So your minimum prefix will become -4 and your minimum index will become six. Okay. Now the final loop which is I= to 6. What is the six element which is one? One is not equals to target. So again you will be subtracting one from it. So it will become -5 and then minimum prefix will become -5 again and minimum index will become 7. Okay. Now this whole loop is done. So what you have to do is you have to come out of the whole thing and you will be returning your answer. So answer is what answer the final answer that you're getting is um 23 which is the maximum value. So the final value that you will be getting here is 23. So 23 is the final answer that you will be getting for this particular question.

[01:25:38]Okay. So this is it. This is how you can do this particular question. And uh we have taken these two questions which already came in infosys exam in the recent shifts. Right? So I hope this video is helpful for you. In the next video I'll be coming with few more questions. Till then keep learning, keep practicing. Thank you.