A min abs slice is a slice whose absolute sum is minimal

ko có cặp (0,4) , (1,2) …vậy ạ.

Họ chỉ đưa ra một số slice thôi, chứ không đưa ra tất cả ở VD Dịch đơn giản đề ra thì là tìm Giá trị tuyệt đối là bé nhất của tổng các số liên tiếp thôi

“Giá trị tuyệt đối là bé nhất” chứ

Thảm nào cứ thắc mắc abs là gì, giờ mới nhớ ra là trị tuyệt đối

làm 2 vòng lặp thì độ phức tạp bao nhiêu vậy ạ, trong trường mình ko dạy kĩ cái này nên giờ cũng ko biết tính

Chạy hết mảng mà 2 vòng lồng nhau thì nhiều khi là O(N^2).

vậy là ko đáp ứng được performance bài này rồi

Đây là cách giải của mình:

1. Xây dựng mảng cộng dồn s[i] = sum(a[0:i])
2. sum(a[p]+a[p+1]+…+a[q]) = s[q+1] - s[p]
3. Từ bước 2 ta thấy là tất cả các đoạn đều có thể tính từ mảng s, mặt khác nếu abs(sum(a[p]+a[p+1]+…+a[q]) ) nhỏ nhất tức là abs(s[q+1] - s[p]) nhỏ nhất hay s[q+1] - s[p] gần 0 nhất
4. Ta chỉ cần sort mảng s để tìm s[q+1] - s[p] gần nhau nhất
5. kết quả = min(sorted_s[i+1] - sorted_s[i])

[details=python]```py

a = [2,-4,6,-3,9]
s = [0]

for w in a:
s.append(s[-1]+w)

s.sort()
ans = float(“inf”)
for i in range(len(s)-1):
ans = min(s[i+1]-s[i],ans)
print(ans)

[/details]

nhỏ nhất hay s[q+1] - s[p] gần 0 nhất

anh gió giải thích em chỗ này với ạ, các phần tử cộng dồn âm dương đâu biết chính xác sao anh xác định chỗ đó gần 0 nhất v. em chưa biết python, trường em dạy mỗi java thôi

Chuyển sang Java nè, nhưng có vẻ không đúng convention lắm.

    int[] sum = new int[numbers.length];
    sum[0] = numbers[0];
    for (int i = 1; i < numbers.length; i++) {
        sum[i] = sum[i - 1] + numbers[i];
    }

    Arrays.sort(sum);

    int minDiff = Math.abs(sum[0]);
    for (int i = 1; i < sum.length; i++) {
        minDiff = Math.min(minDiff, sum[i] - sum[i - 1]);
        minDiff = Math.min(minDiff, Math.abs(sum[i]));
    }

    System.out.println("Min: " + minDiff);
}

</details>

Để giải thích cho bước 3: abs(s[q+1] - s[p]) nhỏ nhất
biểu diễn trên trục tọa độ Ox, abs(a-b) = khoảng cách trên trục tọa độ của 2 điểm a,b
Cố định điểm a, khoảng cách từ a đến các điểm khác nhỏ nhất khi điểm đó gần a nhất

-----------------a----b-----x—y---z------------>

Như vậy đáp số bài toán là khoảng cách nhỏ nhất của 2 điểm liền kề

Giải thích bước 4: sắp xếp lại thứ tự các điểm của mảng s để được các cặp điểm gần nhau