[duyhung123abc]

Đáp án đây

bài 1:
dùng phương pháp đếm, ta sẽ xác định đc trong chuỗi sau cùng tại vị trí nào sẽ có kí tự gì, sau đó, giả sử khoảng trắng đang đứng ở vị trí x, ta tìm trong chuỗi 1 kí tự lẽ ra phải ở vị trí x nhưng đang đứng sai chỗ (nhưng phải tránh kí tự nằm cuối chuỗi nếu tránh đc), ta đổi chỗ kí tự đó và khoảng trắng, cứ tiếp tục như thế. Nếu trường hợp nào đó khoảng trắng nằm cuối chuỗi nhưng chuỗi vẫn chưa đúng thì ta tìm 1 kí tự sai chỗ đổi chỗ nó với khoảng trắng.

Bài 2:
Gọi S[i] là tổng các số trong đoạn 1..i. Ta có thể tính S[i] = S[i-1] + A[i];
Xét những dãy con kết thúc tại i, ta chỉ cần tìm số j sao cho (j<i) và (s[j] nhỏ nhất), khi đó (s[i] - s[j]) chính là tổng đoạn từ (j+1) đến i. Vậy ta lặp 1 vòng for chạy từ đầu đến cuối mảng, biến s là tổng từ 1 đến i, getmin là tổng nhỏ nhất, best là kết quả tối ưu.

s:=0; best:=a[1]; getmin:=0;
for i:=1 to n do
begin
inc(s,a[i]);
if (s-getmin>best) then best:=s - getmin;
if (s<getmin) getmin:=s;
end;
writeln(best);

Bài 3:
Ta lần lượt tách các chuỗi số ra, xóa nó khỏi chuỗi ban đầu và để lại vị trí đó 1 dấu '?', sau khi sắp xếp xong thì chèn số theo thứ tự các vị trí có '?'