So, while working on a problem statement of Euler Project after 30 mins of thinking I came up with an idea that I thought would work, but at the end of all the coding stuff I saw a corner case which made the whole code a claptrap... then after making the necessary changes to cover the corner case, I made the biggest mistake of my day... I missed a '-' in my code, yeah and that took me not less than an hour. It was soo obvious that I just overlooked that part every time while checking my code, and once again I realized that these logical errors are the worst.
I will be working on Python now and then some lessons maybe, well duo is also left for the day, I hope I won't miss the streak. Maybe I will take some more problem statements.
Here is the code of the problem:-
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
int main() {
int T;
cin>>T;
while(T>0){
int n;
cin>>n;
int ind=0;
int ans_sum=0;
vector<vector<int>> vec;
for(int i=0;i<n;i++){
vector<int> te(i+1);
for(int j=0;j<i+1;j++){
cin>>te[j];
}
vec.push_back(te);
}
/***** Waste Approach *****/
// ans_sum=vec[0][0];
// for(int i=1;i<n;i++){
// // for(int j=0;j<i+1;j++){
// //ans_sum+=something;
// if(vec[i][ind]>vec[i][ind+1]){
// ans_sum+=vec[i][ind];
// }
// else {
// ans_sum+=vec[i][ind+1];
// ind=ind+1;
// }
// // }
// }
/**** Bottom-up Approach *****/
// for(int i=n-2;i>=0;i--){
// // int max=0;
// for(int j=0;j<i+1;j++){
// vec[i][j]+=max(vec[i+1][j],vec[i+1][j+1]);
// }
// }
/****** Top-down Approach *******/
for(int i=1;i<n;i++){
for(int j=0;j<i+1;j++){
if(j==0)
{
vec[i][j]+=vec[i-1][0];
}
else if(j==i){
vec[i][j]+=vec[i-1][j-1];
}
else{
vec[i][j]+=max(vec[i-1][j-1],vec[i-1][j]);
}
}
}
int max_elem=0;
// for(vector<int> foo:vec){
// for(int buzz:foo){
// cout<<buzz<<" ";
// }cout<<endl;
// }
for(int i=0;i<n;i++){
if(vec[n-1][i]>max_elem){
max_elem=vec[n-1][i];
}
}
cout<<max_elem<<endl;
// cout<<vec[0][0]<<endl;
T--;
}
return 0;
}
Comments
Post a Comment