Алгоритм Кадана с отрицательными числами, включенными в качестве суммы
//Usually Kadene's algorithm is not considered for negative numbers.
int ms,cs;
ms=cs=a[0];
for(int i=1;i<n;i++)
{
cs=max(a[i],cs+a[i]);
ms=max(cs,ms);
}
return ms;
Crazy Copperhead