Verilen sayılar dizisi (negatif tamsayılar içeren) dizisine, dizideki ardışık öğelerin maksimum toplamını bulduğu bir program yazın.Dizideki öğelerin maksimum toplamını bul
Örnek:
2, 3, -6, -1, 2, -1, 6, 4, -8, 8
verir 11
Ben bir çözüm arıyorum r'den (N^2). Ben Kadane's Algorithm düşünüyorum
Eğer Bu aslında ben (Veri Yapıları ve Algoritmalar Mark Allen Weiss tarafından C) ... Bu çok güzel ve zarif bir çözüm ve çözer üniversitede okudu ders kitabı sorundur
link artık geçerli değil – fayyazkl
istediğim şey o (N)
int MaxSubsequenceSum(int A[])
{
int sum = 0, maxSum = 0;
for (int j = 0; j < A.Length; j++)
{
sum = sum + A[j];
if (sum > maxSum)
maxSum = sum ;
else if (sum < 0)
sum = 0;
}
return maxSum;
}
Yayınınız anonim bir kullanıcı tarafından düzenlendi ve daha sonra onaylandı. Bu değişikliklerin aslında olumlu olduğunu söyleyebilir misiniz? Mantığı önemli ölçüde değiştirmiş görünüyordu. – Gray
hayır Onaylamadım ve cevabı önemli ölçüde geliştirmiyor. Ben –
noktaları için yapıldı düşünüyorum Ben anonim bir kullanıcı tarafından yapıldı, bu yüzden hiçbir rep ödüllendirildi. Geri çekilmek için çekinmeyin. Onlar neden yaptılar hakkında [bir yorum yaptı] (http://stackoverflow.com/posts/12339772/revisions). – Gray
Önce azalan verilen bir diziyi ve daha sonra dizinin ilk üç unsuru Özetle: sum=0 ve baskı toplamı intializing ile sum=arr[0]+arr[1]+arr[2] .
1,2,5,6 ardışık değildir. Alınabilecek alt küme üzerinde herhangi bir kısıtlama yoksa, bu NP-Complete olan Altküme-Sum problemidir, ancak durumun böyle olduğunu düşünmüyorum. – amit
Yanlış anlaşılma için özür dilerim. Açıklamada ve örnekte bir hata yaptım. :) İkisini de güncelledim. – user1106337
Doğrusal bir tarama bu sorunu çözebilir. Sadece toplamı toplayın ve mevcut maks. Ile karşılaştırın, eğer toplamı <0 ise, o zaman toplamı 0'a sıfırlayın ve devam edin. Bu açgözlü çözümün doğru olduğu kanıtlandı. Buna Kadane'nin algoritması deniyor: http://en.wikipedia.org/wiki/Maximum_subarray_problem – nhahtdh