Maximum subarrays problems

#1

What are the constraints what I am not considering I am getting the TLE .

#2

The input constraints ideally are n = [1,100000]
So, Ideally you have to solve the problem in O(n) time complexity you are getting TLE because you are taking O(n^2) time in your solution .
also,I have found some issues with your code try to rectify it

  1. at line 8 of your code you are doing curSum= cumSum[j] - cumSum[i-1];
    but when i=0 , i-1 will evaluate to -1 thus accessing negetive index value in cumSum will give you a garbage value

  2. you have declared your function maxSumsubarrays with return type int but you are not returning any value if you just want to print the value you have to have your return type as void

  3. at line (int arr[100000000]; ) you have declared array size to be very large, for large memory allocation you should use dynammic allocation, but for this problem arr[100001] should suffice

Ask freely if you face any problem

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like
#5

How we can decided the particular solution will be solved in o(n),o(n^2) etc like that.
Can you explain how to know the time complexity of any problem before moving to the solution.

#6

deciding on what time complexity your solution will have is one of the key aspect while solving for a question It can save you from all your TLE troubles .
Now coming to your question that how to determine the time complexity of your solution ,this subject of interest comes under the topic asymptotic notation of Space and Time complexity Ananlysis .
Let me give you little zest of how it works :
Generally your program can execute 10^8 operations in 1 second and most of the time, the time constraint given to you would be 1s then 10^8 operations would be your upper limit .
Now, when you run a loop from 1 to n then n operations will be carried out i.e. under Big Oh notation would be O(n) and when you run a double nested loop (like in your solution) it will take n*(n-1)/2 operations i.e. O(n^2) thus executing (10^5)* (10^5) ( Since,n can take max value of 10^5) =(10^10) which is greater than 10^8 thus taking more than 1s for exection and you will get TLE So, under the given constraints you should have your solution under O(n) (10^5 operations) to O(n* logn) ie ((10^5)*(16.6) < 10^8 which will execute under 1s

#7

this is one amazing vedio by prateek bhaiya that can help you understand this concept

If you face any doubt be free to ask me :slight_smile:

#8

suppose i have given the like :
1<=t<=100
1<=n<=1000
|Ai| <= 10000

How to decided that my solution will not exceed the 10^8 operation ?

#9

total number of operations if you use O(n^2) based solution for this problem will be tnn=100 * 1000 * 1000=10^8 thus can be solved using O(n^2) solution and other with less time complexities

On a side note I want to mention that 10^8 is not a strict upper bound but a good aproximation that you can follow

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#11

thanku so much resolved it can you tell me how to find the hidden test cases in a problem