Help me in solving FINALSALE problem

help
,
1

My issue

whats wrong in my solution

My code

#include <iostream>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--){
	    int n, sum1 = 0, sum2 = 0;
        int c = 0;
        int x = 0;
	    cin >> n;
	    int sale[n] = {0};
	    for(int k = 0; k < n; k++){
	        cin >> sale[k];
	    }
	    for(int i = 0; i < n; i++){ sum1=0;sum2=0;
	        for(int j = 0; j < i; j++){
	            sum1 = sum1 + sale[j];
	        }
	        sum2 = sale[i]*2;
            x = sum1 + sum2;
            if(c < x){
                    c = x;
                }
	    }
	    cout << c <<endl;
	}
}

Problem Link: Sale Practice Coding Problem - CodeChef

2

You logic is correct and effectively solved the problem, BUT you have problems with the implementation. You have 2 issues:

  1. You are dealing with extremelly big numbers (10^9), your ints are overflowing. Get used to using long long
  2. You are using nested loops, making it a O(n*(n+1)//2) algorithm. It’s very heavy and slow, and will get TLE. You have to be efficent (and creative) using your loops wisely.

Why don’t you save your previous sum instead of making a new one each loop? You are going to get the same thing anyway, like this:

#include <iostream>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--){
	    long long  n, sum1 = 0, sum2 = 0;
        long long  c = 0;
        long long  x = 0;
	    cin >> n;
	    long long sale[n] = {0};
	    for(int k = 0; k < n; k++){
	        cin >> sale[k];
	    }
	    
	    long long prevSum = 0;
	    
	    for(int i = 0; i < n; i++){ //sum1=0;sum2=0;
	    
            sum1 = prevSum;
            sum2 = sale[i]*2;
            
	        x = sum1 + sum2;
            if(c < x){
                c = x;
            }
            prevSum += sale[i];
            
	    }
	    cout << c <<endl;
	}
}