Can you tell me my mistake for FINALSALE code

general
,
1

include <bits/stdc++.h>

using namespace std;

int main() {
int t;
cin >> t;
while (t–) {
int n;
cin >> n;
vector v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
auto max = max_element(v.begin(), v.end());
int sum = accumulate(v.begin(), max, 0);
sum += 2 * (*max);
cout << sum << “\n”;
}

return 0;

}

2

You are assuming the max day is the best day to close up the store, which is wrong. Say:

A = [1,1,1]
max = (iterator for the 1st index) → Only takes the first appereance of the biggest
sum = 1 (since only sum the first element)
sum = 1 + 2*1

cout << 3 << “\n”

But the right answer is 4: 1+1+2 (closing the last day).

You didn’t have to assume the day of max sales was the best. You had to try a O(n) algorithm to try out all the possibilities, like this:

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        
        int n;
        cin >> n;
        vector<long long> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
        }
        
        //auto max = max_element(v.begin(), v.end());
        //int sum = accumulate(v.begin(), max, 0);
        // You can't assume the max day is the best day,
        
        long long maxSales = 0;
        long long prev = 0;
        for(int i=0; i<n; i++){
            maxSales = max(maxSales, prev + v[i]*2);
            prev += v[i];
        }
        //sum += 2 * (*max);
        cout << maxSales << "\n";
    }
    
    return 0;
}