Въпрос относно последователност от числа в масив
Здравейте,
Решавайки една от задачите в глава 7. Масиви от "Въведение в програмирането със С#" се сблъсках трудност относно разбирането на логикатата й и не успях да я реша. Става въпрос за задача 9. Напишете програма, която намира последователност от числа, чиито сума е максимална.
Пример: {2, 3, -6, -1, 2, -1, 6, 4, -8, 8} = 11.
След като намерих едно от възможните й решения, се помъчих да открия логиката как точно се достига до крайния верен резултат, но без успех. Блъсках си главата, но нищо не мога да разбера, а изглежда доста кратък и лесен код.
Да поясня, всички въпроси и коментари, които имам към кода, са с примерните числа от масива в задачата.
int sum = 0, tempSum;
Console.Write("Enter array length: ");
int length = Int32.Parse(Console.ReadLine());
int[] arr = new int[length];
for (int i = 0; i < length; i++)
{
Console.Write("Enter {0} element: ", i);
arr[i] = Int32.Parse(Console.ReadLine());
}
for (int i = 0; i < length - 1; i++) // ако вземем числата в условието, то в началото i = 2.
{
tempSum = arr[i]; // следователно тук tempSum = 2.
for (int j = i + 1; j < length; j++) // ако вземем числата в условието, то в началото j = 3.
{
tempSum += arr[j]; // тук tempSum = 2 + 3 = 5.
if (tempSum > sum) //тук tempSum е 5, а не 2, ако правилно разсъждавам. 5 > 0, тъй като sum = 0.
{
sum = tempSum; // от тук следва, че sum = 5.
}
}
}
Console.WriteLine("Result is {0}. ", sum);
Ако коментарите са ми верни. То при следващата итерация на вътрешния for loop:
j = -6, tempSum = 2 + (-6) = -4, ако взема стойността на sum от предната итерация то би трябвало да е равен на 5 и няма да се изпълни if-a.
При следващо завъртане на вътрешния цикъл:
j = -1, tempSum = 2 + (-1) = 1, тук sum коя стойност взема, тази от предната итерация ли, т.е. няма как да го вземе тъй като не се е изпълнил if-a, значи взима от първата и е равен на 5, и пак няма да се изпълни if-a, защото 1 < 5?
Така продължавам до края на вътрешния цикъл, после външния се завърта и вече i = 3, tempSum = 3. А j = -6, tempSum = 3 + (-6) = -3 и вече не знам sum на какво е равно.
Просто много се обърках. Явно не мисля в правилната посока.
Ако някой може да ми обясни логиката на двата цикъла и как точно се извършват итерациите във вътрешния цикъл, външния и съответно какви са стойностите които приемат tempSum при i, tempSum при j и sum.
Благодаря предварително.
Много благодаря за обясненията.
Искам обаче да ти кажа какви са въпросите, на които не си давам еднозначен отговор.
1. Доколкото разбирам още при първото пълно завъртане на вътрешния цикъл се достига маскималната сума 11, при j = 7. И това означава, че при всички следващи завъртания на външния цикъл и вътрешния, маскималната сума няма да превиши 11?
2. При j = 9 от първото завъртане на вътрешния цикъл отново се достига маскималната сума 11, но понеже sum приема стойността на tempSum, само ако tempSum > sum (а sum вече е 11 от завъртането при j = 7), то няма как sum да приеме отново 11. Правилна ли ми е логиката?
3. При условие, че sum приема максималната си стойност (при j = 7) само ако е по-малка от текущата стойност на tempSum, не успях да разбера как тя (стойността на sum) е равна на сбора от стойностите на числата 2, -1, 6 и 4? Освен това, последното което написа: "Т.е. ако гледахме и откъде започва и къде свършва тази въпросна последователност, щеше да трябва да покажем и двете: от индекси 4 до 7 и от 4 до 9. Но ние не пазим позициите, а само максималната сума, затова всичко си е наред. " също не успях да го разбера или може би отговорът е във въпрос № 2, ако правилно съм разсъждавал.
Моля :)
1. Това е така по чиста случайност, защото последните две числа са -8 и 8. Ако последното не беше 8, а 6, нямаше да достигне 11 още при първото завъртане на вътрешния цикъл.
2. Да. sum ще се промени, само ако tempSum > sum.
3. Защото, когато i = 4 и j = 7, тогава в tempSum сме сумирали само числата от arr[4] до arr[7] вкл., които са точно 2, -1, 6, 4 и тогава за първи път попадаме на сума 11, която се явява максималната досега. В този момент sum си я взима и я запазва като най-голяма среана последователна сума. В следващите две итерации на j цикъла, tempSum се намалява веднъж с 8, после се увеличава пак с 8 и отново стига 11, но това няма да промени sum (заради отговора на въпрос 2, да). Така фактически sum продължава да пази само сумата на четирите изброени числа.
4. А относно онова, което съм написала, не го мисли сега. То искаше да каже, че ако трябва да знаем и къде започва и къде свършва въпросната последователност, щеше да трябва да покажем и двете: 2, -1, 6, 4 и 2, -1, 6, 4, -8, 8, защото и двете дават 11. Но на нас ни трябва само числото 11, затова всичко, което е по-малко или равно на него, не го променя.
Пиши, ако има още нещо.
Мисля, че вече ми се изясниха нещата.
Относно дебъгера,... от това което пишеше в книгата, бях останал с впечатление, че се използва само ако има грешки и искаме да ги открием. Сега обаче го пробвах и наистина виждам логиката съпка по стъпка.
Благодаря ти, отново.