leetcode_solutions/Ninjas_Training.cpp at main · ar-zoop/leetcode_solutions · GitHub

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
#include <bits/stdc++.h>
using namespace std;

int memo[100000][4];
int sub(int idx, int task, vector<vector<int>> &points, int n){
    int left,right;
    //base case

    if(idx>n-1){
        return 0;
    }
    if(memo[idx][task]!=-1)return memo[idx][task];
     if(task==0){
        //left
        left= sub(idx+1,2, points, n )+points[idx][task];
        //right
        right= sub(idx+1,1, points, n )+points[idx][task];
        // return max(left, right);
    }

    if(task==1){
        //left
        left= sub(idx+1,2, points, n  )+points[idx][task];
        //right
        right= sub(idx+1,0, points, n )+points[idx][task];
        // return max(left, right);
    }

     if(task==2){
        //left
        left= sub(idx+1,0, points, n  )+points[idx][task];
        //right
        right= sub(idx+1,1, points, n )+points[idx][task];

    }
    return memo[idx][task]=max(left,right);
}

int ninjaTraining(int n, vector<vector<int>> &points)
{
    // Write your code here.
    int max=INT_MIN;
    memset(memo, -1, sizeof(memo));
    for (int i=0;i<3;i++){
        int jump=sub(0,i, points, n);
        if(jump>max)max=jump;
    }
    return max;
}