Просили подробно про интервью в Google...

[febb]

Гуглята издеваются на интервью. Например они задают такие классические задачки.

Дан массив целых чисел (положительные и отрицательные) найти кусок в этом массиве,
сумма элементов в котором максимальная.

Это известная задачка. Поэтому кто знает ответ, не залезая в Гугл,
может просто написать тут "знаю". Это своеобразные азы, ликбез
для молодого гугловода... :)

А кто не знает, можете предложить алгоритм тут.
Нам будет забавно узнать какие вы умные. :))

Comments

[leeeto.livejournal.com]

омг. вот мой вариант :)
нужен пост про правильно :)

<%


//int arr[]={-1,0,2,7,-10,8,4,3,-4,1};

int arr[]={3,0,2,-7,5,-8,4,3,-4,1};

int max = 0, sum = 0, step=0, firstpos = 0, a=0, b=0;
for (int i=0;i<10;i++)out.println(arr[i]+" ");
out.println("
");

boolean isfirst=true;
if(arr[1]<0)isfirst=false;

for (int i=0;i<10;i++)
{
if (arr[i]<0) {
if(sum>max)
{
max=sum;
a=firstpos;
b=firstpos+step-1;

}

sum=0;
isfirst=true;
step=0;
}
else {
if(isfirst) {
firstpos=i+1;
step=0;
isfirst=false;
}
sum = sum+arr[i];
step++;
}

}

out.println("max= "+max+" a = "+a+ " b= "+b);

%>

[febb.livejournal.com]

У меня тоже была сначала идея, что нужно искать по отрицательным элементам.
Но это на самом деле не так. Ведь за небольшим отрицательным может быть очень хорошее положительное!
Надо быть оптимистом! :)
Спасибо!

[leeeto.livejournal.com]

хм.
а ведь вы правы. :)))))))))

ладно. буду думать дальше.