Dec 2021
1 / 4
Jan 2022
Jan 2022
anit_mangal15
Dec '21

Used a trivial approach for solving using dp which would iterate twice through the vector. I can’t find what’s causing SIGABRT in this though

#include <bits/stdc++.h>
using namespace std;
long long int solver(int n){
if (n == 0) return 0;
vector monster;
long long int s;
for (int i = 0; i < n; i++) {
cin >> s;
monster.push_back(s);
}
if (n == 1) return monster[0];
long long int totalmax = max(monster[0], monster[1]);
vector maxvec{monster[0], monster[1]};
for (int i = 2; i < n; i ++) {
long long int tempmax = 0;
for (int j = 0; j < i-1; j++) if (tempmax < maxvec[j]) tempmax = maxvec[j];
maxvec[i] = tempmax + monster[i];
if (totalmax < maxvec[i]) totalmax = maxvec[i];
}
return totalmax;
}

int main() {
int t;
cin >> t;
for (int i = 1; i <= t; i++){
int n;
cin >> n;
long long int res = solver(n);
cout << "Case " << i << ": " << res << endl;
}
}

  • created

    Dec '21

  • last reply

    Jan '22
  • 3

    replies

  • 785

    views

  • 2

    users

simes
Dec '21

Within the Solve method, you’re accessing indices of the maxvec vector that don’t exist.

In this loop, check the number of elements in the vector against the index.

for (int j = 0; j < i-1; j++) if (tempmax < maxvec[j]) tempmax = maxvec[j];

Try this test case

1
10
1 1 1 4 1 7 19 1 1 2

anit_mangal15
Jan '22
#include <bits/stdc++.h>
using namespace std;
long long int solver(int n){
	if (n == 0) return 0;
	vector <long long int> monster;
	long long int s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		monster.push_back(s);
	}
	if (n == 1) return monster[0];
	long long int totalmax = max(monster[0], monster[1]);
	vector <long long int> maxvec{monster[0], monster[1]};
	for (int i = 2; i < n; i ++) {
		long long int tempmax = 0;
		for (int j = 0; j < i-1; j++) if (tempmax < maxvec[j]) tempmax = maxvec[j];
		maxvec[i] = tempmax + monster[i];
		if (totalmax < maxvec[i]) totalmax = maxvec[i];
	}
	return totalmax;
}

int main() {
	int t;
	cin >> t;
	for (int i = 1; i <= t; i++){
		int n;
		cin >> n;
		long long int res = solver(n);
		cout << "Case " << i << ": " << res << endl;
	}
}

There was an issue with the formatting in my original post. I had defined the maxvec vector. The test case you provided run smoothly with the above code and gave 26, however, it still shows SIGABRT when I submit it.

simes
Jan '22

I still think you’re accessing elements of the maxvec vector that don’t exist.

replace

maxvec[i] = tempmax + monster[i];

with

maxvec.push_back(tempmax + monster[i]);

There should probably be a return 0; at the end of main( ) too.