pub fn max_subarray(nums: &[i64]) -> Option<(i64, usize, usize)>Expand description
Kadane algoritmi — eng katta yig’indili qism-massiv (maximum subarray).
G’oya: har bir pozitsiyada bitta savol beramiz — “oldingi yig’indini davom ettirish foydalimi yoki shu yerdan yangi boshlash yaxshiroqmi?” Agar oldingi yig’indi manfiy bo’lsa, uni sudrab yurishdan foyda yo’q.
- Time: O(n), Space: O(1) — DP ning eng nafis namunasi.
Qaytadi: (yig'indi, boshlanish_indeksi, tugash_indeksi_inklyuziv).
Bo’sh massivda None.
§Misol
use rust_algorithms::dp::max_subarray;
let v = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
assert_eq!(max_subarray(&v), Some((6, 3, 6))); // [4, -1, 2, 1]
// hammasi manfiy bo'lsa — eng katta (eng kam manfiy) element
assert_eq!(max_subarray(&[-5, -2, -9]), Some((-2, 1, 1)));
assert_eq!(max_subarray(&[]), None);