18-08-2006, 16:31
|
 |
|
|
חבר מתאריך: 15.08.06
הודעות: 465
|
|
|
כמעט :)
ציטוט:
|
במקור נכתב על ידי Urikiller
מתחילים מהאיבר הראשון והולכים קדימה עד שפוגשים איבר שלילי וכל הדרך גם סופרים את הסכום.
אחרי זה ממשיכים עוד פעם קדימה (מדלגים קדימה על האיבר השלילי) עד שפוגשים עוד פעם איבר שלילי.
בודקים אם הסכום החדש יותר מהישן (שומרים את הסכום החדש במשתנה אחר).
אם כן, הסכום הישן מקבל את הערך של הסכום החדש.
ככה ממשיכים עד הסוף ויש את הסכום הכי גדול.
בזמן כל התהליך הזה גם אפשר לשמור כל פעם איפה מתחיל ונגמר התת מערך עם הסכום הכי גדול עד עכשיו.
ככה יהיה אפשר לדעת איפה נמצא התתתתת-מערך הכי גדול.
זה הפתרון שחשבת עליו?
|
מה שכתבת יעבוד על עוד במערך לא קיים סכום חיוביים שהאיבר השלילי אחריו + הסכום יהיה גדול מ0...שהרי אז אתה בודק סכום, מגיע לאיבר שלילי, בודק את סכום כל האיברים אחריו עד האיבר השלילי הבא - אם קיים, ואז אתה לוקח את הסכום הגדול מבין הסכומים, למרות שאתה צריך לכלול את סכום שני הסכומים + האיבר השלילי הראשון, (ויכול להיות השני, על אותו עקרון).
מה שצריך לעשות, מאוד מאוד, מאוד פשוט 
אתה עובר על המערך ומחשב סכום עד המיקום הנוכחי, ברגע שהסכום קטן מ0, אתה מאפס את הסכום, וממשיך.
קוד:
int MaxSubArr(int len, int *first)
{
int biggest = 0
int sum = 0;
int i = 0;
for(i = 0; i < len; ++i)
{
sum += *(first + i);
if(sum < 0)
{
sum = 0;
}
biggest=biggest > sum ? biggest:sum;
}
return biggest;
}
_____________________________________
Any sufficiently advanced bug is indistinguishable from a feature
|
ראשי
צ'אט
)
מצב כלאיים
