I dont know how to fix the time complexity when they ask for various test cases

#1

HI! this is my code and I know that it has something to do with variable t i.e. test case. Following is my code.

#include
using namespace std;

int main()
{
int t;
cin>>t;
int a=1;
while(a<=t)
{
int n;
int max = 0;
cin>>n;
int arr[100000];
for (int i=0;i<n;i++)
{
cin>>arr[i];
}
int curr[100000];
curr[0] = arr[0];
int sum;
for (int i=1;i<n;i++)
{
curr[i] = curr[i-1] + arr[i];
}
for (int i=0;i<n;i++)
{
for (int j=i;j<n;j++)
{
sum = curr[j] - curr[i-1];
if (sum>max)
{
max = sum;
}
}
}
cout<<max<<endl;

}
return 0;

}

#3

Hey @nikunjj44
You have implemented O(n^2) approach to find maximum sum but instead u have to implement O(n) Kadane algo in this question.
Kadane is a part of your course so my suggestion is skip this for now and come back to this later :slight_smile:
If this resolves your query then please mark it as resolved :slight_smile:

#4

ohh okay ill try that. So usually in questions in which test cases are given by user, so we always use O(n) ?

#5


This is my method, so I always use this type of approach for those questions?

#6

No bro
N is 10^5 so n^2 will be 10^10 and max we can run for is 10^8
So thats why n^2 will fail

Always measure the total complexity
Here it will be O(tn) for kadane and it should be less than equal to 10^8

#7

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.

#8

hey i tried this using kodane its still giving time exceeded

#9

Hey @nikunjj44
what is the issue?

#10

please share your code.

#11

https://ide.codingblocks.com/s/359726 This is my code

#12

u forgot to do a++

if problem still persist then let me know :slight_smile:

#13

You also forgot to print ans

  cout<<msum<<endl;
#14

Yes it worked. Thank You!!

1 Like