Mọi người cho e xin ý tưởng QHĐ bài này với ạ. E cảm ơn
Cho dãy số A có N phần tử, đánh số từ 1 đến N. Mỗi lần loại một vị trí i ra khỏi dãy (1 < i < N) thì ta sẽ có thêm một giá trị được tính bằng tích của A[i-1] * A[i+1]. Sau đó các số còn lại trong dãy lại được đánh số lại từ đầu.
Dễ dàng nhận thấy ta sẽ không thể lấy ra được hai số đầu và cuối dãy nên khi chỉ còn hai số này thì sẽ kết thúc.
Hãy tính tổng giá trị lớn nhất có thể thu được.
Input
Dòng đầu tiên ghi số N (3 ≤ N ≤ 100)
Dòng tiếp theo ghi N số của dãy A (1 ≤ A[i] ≤ 1000)
Output
Ghi ra tổng giá trị lớn nhất có thể đạt được.
Example:
Input
5
8 2 4 1 3
Output: 68
Giải thích:
Dãy số ban đầu là 8 2 4 1 3
- Loại bỏ số 2: sum=8.4=32, dãy số mới: 8 4 1 3
- Loại bỏ số 1: sum=32+4.3=44, dãy số mới: 8 4 3
- Loại bỏ số 4: sum=44+8.3=68, dãy số mới: 8 3