Xét tất cả các cặp \(1 \leq i \leq j \leq N\) và duyệt từ \(i\) đến \(j\) để tính tổng của đoạn \([i,j]\) và kiểm tra xem có thoả mãn điều kiện đề bài hay không.
Độ phức tạp thời gian : \(O(N^3)\)

Ý tưởng tương tự Subtask \(1\), tuy nhiên ta cần tính tổng đoạn \([i..j]\) trong \(O(1)\) bằng cách khi \(j\) đi qua phần tử nào thì ta cộng phần tử đó vào tổng \([i..j]\)
Độ phức tạp thời gian \(O(N^2)\)

Với \(\sum_{i=1}^{n}\), ta sẽ tìm vị trí \(j \leq i\) lớn nhất mà thoả mãn điều kiện bằng cách chặt nhị phân.
Nói cách khác, gọi \(prefix(i,j)\) là tổng các phần tử trong đoạn \([i..j]\), ta tìm \(j \leq i\) lớn nhất sao cho \(prefix(j,i) \geq S\).
Độ phức tạp thời gian: \((O(N.log_2(N))\)

Áp dụng ý tưởng của Subtask \(3\), tuy nhiên ta thấy rằng nếu đoạn \([j..i]\) thoả mãn thì \(\sum_{k=i}^{n}\) \(prefix(j,k)\) đều thoả mãn, nên ta sẽ sử dụng hai con trỏ.
Độ phức tạp thời gian: \(O(N)\)