-
Notifications
You must be signed in to change notification settings - Fork 0
/
maximum-path-sum-i.cpp
50 lines (46 loc) · 1.16 KB
/
maximum-path-sum-i.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// https://www.hackerrank.com/contests/projecteuler/challenges/euler018/problem
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
void find(ll &ans, vector < vector < ll > > &v , ll n , int i , int j ,ll sum)
{
//cout << i << " " << j << endl;
sum += v[i][j];
ans = max(ans , sum);
if(i + 1 !=n )
{
find(ans , v , n , i + 1 , j , sum);
find(ans , v , n , i + 1 ,j + 1, sum);
}
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
ll t;
cin >> t;
while( t-- )
{
ll n;
cin >> n;
int count = 1;
vector < vector < ll > > v ;
ll x1 = n;
while( n-- )
{
int i = 0;
vector < ll > temp;
while( i < count)
{
ll x;
cin >> x;
temp.push_back(x);
i++;
}
v.push_back(temp);
count ++;
}
ll ans = 0;
find(ans , v , x1 , 0, 0 , 0);
cout << ans << endl;
}
return 0;
}