# Largest Sum of a Path in a Triangle

Given a file consisting a pascals-like triangle of integers separated by spaces, return the sum of the path with the largest sum, as well as the final column index in the triangle. A **path** can only iterate down to the next level below to its **child**. Each **parent** shares 2 **adjacent children** in the level below. e.g. in the second row parent 2 shares children 2 and 3 and parent 3 shares shares children 3 and 4.

Note: integers can be `>9` and `<0`.

Visually:

```
     1
    2 3 
   2 3 4 
  2 3 5 7  
 2 3 4 2 1 
6 6 4 8 3 2
```

Actually:

```
1
2 3
2 3 4
2 3 5 7
2 3 4 2 1
6 6 4 8 3 2
```

output:

```
25 3
```

Explanation: The sum of the max path is 25, and the column it end with is @index 3, which contains integer `8`. The reason why we want to return the column index is because we can use it as information to backtrace back up the tree and return the actual path. Observe:

```
1
      3 
       4 
        7  
       2 
      8
```

This is done by taking the number at said column and then selecting the maximum of one of its two parents.

**The Idea:**

* We can structure the information into a binary tree then do a path traversal to the leaf node, but in my opinion this would be a lot more difficult to parse, we can just use BFS iteratively.
* First I parse the information into an indexable 2 dimensional vector. Then I begin the BFS procedure using an object of type `Node` that will carries information about the particular index. `cur_sum` is preferably important because it allows be to dynamically refer back to the previous sum. This works because the associative property of addition tells us that `2 + 3 + 5 = 3 + 2 + 5`, i.e. permutations don't matter. The `row` and `col` information is used to refer to the next index in the 2d array. I know for a fact that it will be in the next row down, same col and an additional column forward.

```cpp
vector<int> parse_line(const string &line, const char delimitor = ' ')
{
    vector<int> line_ints;
    stringstream ss(line);
    string cur_int;

    while (getline(ss, cur_int, delimitor)) {
        int to_int = stoi(cur_int.c_str());
        line_ints.push_back(to_int);
    }
    return line_ints;
}

vector<vector<int>> parse_file(const string &f_path)
{
    vector<vector<int>> triangle;
    vector<int> temp;

    ifstream infile(f_path);
    if (infile.good()) {
        string cur_line;
        while (getline(infile, cur_line)) {
            triangle.push_back(parse_line(cur_line));
        }
    }
    return triangle;
}

struct Node
{
    int num, row, col, cur_sum;;
};

pair<int, int> max_tri_sum(const string &f_path)
{
    vector<vector<int>> all_data = parse_file(f_path);

    int cur_max = INT_MIN;
    int cur_max_col_i = 0;
    queue<Node> q;

    int cur_data = all_data[0][0];
    int cur_row = 0;
    int cur_col = 0;
    int cur_sum = cur_data;

    q.push(Node{ cur_data, cur_row, cur_col, cur_sum });

    while (!q.empty()) {
        Node cur_front = q.front();
        q.pop();

        if (cur_max < cur_front.cur_sum) {
            cur_max = cur_front.cur_sum;
            cur_max_col_i = cur_front.col;
        }

        if (cur_front.row + 1 < all_data.size()) {
            cur_data = all_data[cur_front.row + 1][cur_front.col];
            cur_row = cur_front.row + 1;
            cur_col = cur_front.col;
            cur_sum = cur_data + cur_front.cur_sum;

            q.push(Node{ cur_data, cur_row, cur_col, cur_sum });

            cur_data = all_data[cur_front.row + 1][cur_front.col + 1];
            cur_row = cur_front.row + 1;
            cur_col = cur_front.col + 1;
            cur_sum = cur_data + cur_front.cur_sum;

            q.push(Node{ cur_data, cur_row, cur_col, cur_sum });
        }
    }

    return {cur_max, cur_max_col_i};
}

int main()
{
    pair<int, int> sum_col = max_tri_sum("../infile/triangle.txt");
    cout << sum_col.first << " "  << sum_col.second << endl;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/recursion-and-dynamic-programming/largest-sum-of-a-path-in-a-triangle.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.