Tư duy lập trình tốt và thiết kế giải thuật tối ưu là những kỹ năng quan trọng trong lĩnh vực lập trình, là nền tảng tốt để các bạn sinh viên có thể tham gia nghiên cứu khoa học.

Năm học 2023-2024, Thầy Tùng muốn tuyển chọn các bạn có khả năng nghiên cứu khoa học bằng cách đưa ra một bài toán trên tam giác số với yêu cầu: Tìm tổng lớn nhất các số trên con đường bắt đầu từ đỉnh đầu của tam giác và kết thúc ở bất kì đỉnh nào ở đáy:

Biết rằng:

• Mỗi bước có thể đi chéo xuống phía trái hoặc đi xuống phía phải
• Số lượng dòng trong tam giác 1 < N ≤ 100
• Các số trong tam giác đều là số nguyên dương từ 0 đến 99.

• Dòng 1: Chứa số N là số dòng của tam giác
• N dòng tiếp theo, ứng với mỗi dòng thứ i sẽ có i số nguyên dương cách nhau bằng khoảng trắng.

Tổng đoạn đường dài nhất tìm được.

Tam giác đi theo đường 7-3-8-7-6 để được tổng 31 là dài nhất cần tìm.