Cho dãy số nguyên gồm n phần tử a₁, a₂, …, a_n  (1 £ n £ 10⁵) và hai số nguyên dương p và q (1 £ p £ q £ n).

Yêu cầu: Hãy tính tổng của các phần tử liên tiếp từ  a_p … a_q  bằng phương pháp quy hoạch động (lập bảng phương án).

Dữ liệu vào: Ghi trong file văn bản SUM.INP có cấu trúc như sau:

- Dòng 1: Ghi số nguyên dương n và k, hai số được ghi cách nhau một dấu cách.

- Dòng 2: Ghi n số nguyên a₁, a₂, …, a_n, các số được ghi cách nhau ít nhất một dấu cách (-32000 £ a_i £ 32000).

- Dòng thứ i trong k dòng tiếp theo: Mỗi dòng ghi hai số nguyên dương p_i và q_i, hai số được ghi cách nhau một dấu cách (1 £ p_i £ q_i £ n).

Dữ liệu ra: Ghi ra file văn bản SUM.OUT theo cấu trúc như sau:

- Dữ liệu được ghi trên k dòng: Dòng thứ i ghi một số nguyên là tổng giá trị của các phần tử trong đoạn

Ví dụ:

Thuật toán:

          Gọi A[i] là giá trị của phần tử thứ i trong dãy số a₁, a₂, …, a_n.

Gọi T[i] là tổng giá trị các phần tử a₁, a₂, …, a_i  (1 £ i £ n).

          Ta có công thức quy hoạch động để tính T[i] như sau:

                    T[i] := T[i - 1] + A[i];

          Như vậy, việc tính T[n] được thực hiện bằng vòng lặp:

                    T[0] := 0;

For i:=1 to n do

          T[i] := T[i - 1] + A[i];

          Kết quả: Tổng các phần tử liên tiếp từ  a_p đến a_q được tính theo công thức:

                    Sum := T[q] - T[p-1];