Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Here is an excellent blog post on this topic http://wordaligned.org/articles/the-maximum-subsequence-problem
The solution could be:int vect[] = {1,1,2,1,1,1,1,3,3,3,2};int cont_seq_sum(int vect[], int size) { int sum = vect[0]; int max = sum; for (int i=0; i max ) max = sum; } return max;}int main( int argc, char* argv[] ){ std::cout << max_cont_seq(vect,sizeof(vect)/sizeof(int)) << std::endl; std::cout << cont_seq_sum(vect,sizeof(vect)/sizeof(int)) << std::endl; return 0;}
I guess you contented in reading the book Programming Pearls by Bentley. One column was dedicated to this algorithm. I am providing the code.int max_subarray_kadane_algo(int array[], int size){ int max_sofar = 0; int max_ending_here = 0; int index; for(index = 0; index < size; index++) { max_ending_here = max(0, max_ending_here + array[index]); max_sofar = max(max_sofar, max_ending_here); // Visulise the algorithm cout << "Element " << array[index] << endl; cout << "max_ending_here " << max_ending_here << endl; cout << "max_sofar " << max_sofar << endl << endl; } return max_sofar;}int main(){ // Exercise problem from Algorigthms by Das Gupta int data[] = {5, 15, -30, 10, -5, 40, 10}; int size = sizeof(data)/sizeof(data[0]); cout << "Result " << max_subarray_kadane_algo(data, size);}
Here is an excellent blog post on this topic http://wordaligned.org/articles/the-maximum-subsequence-problem
ReplyDeleteThe solution could be:
ReplyDeleteint vect[] = {1,1,2,1,1,1,1,3,3,3,2};
int cont_seq_sum(int vect[], int size)
{
int sum = vect[0];
int max = sum;
for (int i=0; i max )
max = sum;
}
return max;
}
int main( int argc, char* argv[] )
{
std::cout << max_cont_seq(vect,sizeof(vect)/sizeof(int)) << std::endl;
std::cout << cont_seq_sum(vect,sizeof(vect)/sizeof(int)) << std::endl;
return 0;
}
I guess you contented in reading the book Programming Pearls by Bentley. One column was dedicated to this algorithm. I am providing the code.
ReplyDeleteint max_subarray_kadane_algo(int array[], int size)
{
int max_sofar = 0;
int max_ending_here = 0;
int index;
for(index = 0; index < size; index++)
{
max_ending_here = max(0, max_ending_here + array[index]);
max_sofar = max(max_sofar, max_ending_here);
// Visulise the algorithm
cout << "Element " << array[index] << endl;
cout << "max_ending_here " << max_ending_here << endl;
cout << "max_sofar " << max_sofar << endl << endl;
}
return max_sofar;
}
int main()
{
// Exercise problem from Algorigthms by Das Gupta
int data[] = {5, 15, -30, 10, -5, 40, 10};
int size = sizeof(data)/sizeof(data[0]);
cout << "Result " << max_subarray_kadane_algo(data, size);
}