Algoritmul lui Kadane

• Algoritm eficient, epntru determinarea cea mai lunga subsecevnta cu suma maxima
• Complexitate : O(n)
• Cod C++:

int kadane(int vec[], int s){ int sum = -1, maxi = -20000000; for(int i = 1; i <= s; i++){ if(sum < 0) sum = 0; sum += vec[i]; if(sum > maxi) maxi = sum; } return maxi;
}