Thắc mắc về bài toán dãy con có tổng bằng S

#1

Em nghĩ hoài nhưng vẫn không hiểu chổ này: “Hãy tự kiểm tra xem tại sao vòng for thứ 2 lại là for downto chứ không phải là for to.”
Mấy anh chị có thể giải thích giúp em không?? em yếu QHĐ lắm ạ :((

#2

Bởi nếu dùng for to giả sử L[t]=1 thì sẽ dẫn đến L[t+a[i]]=1,L[t+a[i]+a[i]]=1… Do for to,a[i] dc sử dụng nhiều hơn 1 lần. Còn for down to để hình thành tổng t, a[i] chỉ sử dụng 1 lần Bởi t-a[i] trước đó đã có và a[i]

1 Like
#3

nhưng nếu mình xài công thức trên ảnh nhưng dùng for to thì sẽ sai ở chỗ nào ạ?

1 Like
#4

Như giải thích ở trên thì for to cũng sẽ hình thành tổng S nhưng a[i] có thể sử dụng nhiều lần, trong khi đề bài là a[i] chỉ dùng tối đa 1 lần

1 Like
#5

Bỏi vì để có những slot phía sau thì phải có slot đầu vì vậy phải tính từ lớn đến bé.

p/s: làm như vầy sẽ là O(n*delta_S) time và O(delta_S) space với delta_S = sum+(a) - sum-(a)

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?