Skip to content

Instantly share code, notes, and snippets.

@arrayed
Created December 26, 2016 18:46
Show Gist options
  • Save arrayed/efa7cc2f32319205238c37a298f5cafc to your computer and use it in GitHub Desktop.
Save arrayed/efa7cc2f32319205238c37a298f5cafc to your computer and use it in GitHub Desktop.
Find maximum of subarray - Arrayed.Net
//============================================================================
// Name : MaxSubarray.cpp
// Author : Amritpal Singh
// Version : v0.1
// Copyright : arrayed.net
// Description : Find maximum of subarray.
//============================================================================
#include <iostream>
using namespace std;
int max_subarray_sum(int arr[], int size);
int main() {
int a[] = {3, 4, -6, 2, -5, 8, -3, 9, -4, 3};
int n = sizeof(a)/sizeof(a[0]);
cout << "Max of array a[] is " << max_subarray_sum(a,n) << endl;
return 0;
}
int max_subarray_sum(int arr[], int size)
{
int max_sum = 0;
int new_max_sum = 0;
for (int i=0; i<size; i++)
{
new_max_sum += arr[i];
if (new_max_sum < 0)
new_max_sum = 0;
if (max_sum < new_max_sum)
max_sum = new_max_sum;
}
return max_sum;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment