Nhận xét 1:

• Công thức cần tối ưu là \(S - (A_{max} - A_{min})\) với \(S\) là tổng các \(B_i\) được chọn.
• Vì các \(B_i\) luôn luôn lớn hơn \(0\) nên nếu chọn 2 phần tử \(i\) và \(j\) (\(i < j\)) trên mảng phần tử đã được sort lại theo \(A\) thì luôn luôn có thể chọn thêm các phần tử nằm ở giữa \(i\) và \(j\) vì giá trị \((A_{max} - A_{min}\)) không thay đổi (\(A_{max} = A_j, A_{min} = A_i\)) còn \(S\) thì tăng. Vậy thì đáp án tối ưu luôn luôn là một dãy các giá trị liên tiếp trên mảng đã được sort lại theo \(A\).

Lời giải:

• Vì các phép toán là tổng các phần tử trên đoạn nên sẽ sử dụng tổng tiền tố.
• Gọi \(S[i]\) là tổng các \(B_j\) (\(1 \leq j \leq i\)), cần tìm cặp số \(i\) và \(j\) sao cho \((S[j] - S[i - 1]) - (A[j] - A[i])\) là lớn nhất.
• Sắp xếp lại các hạng tử, ta có: \((S[j] - A[j]) - (S[i - 1] - A[i])\), vậy thì với mỗi \(j\) ta cần tìm \(i\) (\(1 \leq i \leq j\)) sao cho giá trị \((S[i - 1] - A[i])\) là bé nhất bằng cách sử dụng min tiền tố.
• Vậy bài toán trên đã được giải với độ phức tạp \(O(N)\)