Question

Consider a sequence of 14 elements: A = [−5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0].

The subsequence sum \(S\left( {i,j} \right) = \mathop \sum \nolimits_{k = i}^j A\left[ k \right]\). Determine the maximum of S(i, j),

where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used.)

Answer 1

Largest Sum Contiguous subarray is from index 2 to 11

Maximum subsequence sum = S(2, 11) = 6, 3, -1, -2, 13, 4, -9, -1, 4, 12 = 29

Code in C++ to find the maximum contiguous sum of array

#include <iostream>

using namespace std;

int kadane(int arr[], int n)

{

int max_so_far = 0;

int max_ending = 0;

for (int i = 0; i < n; i++)

{

max_ending = max_ending + arr[i];

max_ending = max(max_ending, 0);

max_so_far = max(max_so_far, max_ending);

}

return max_so_far;

}

int main()

{

int arr[] = { −5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0};

int n = sizeof(arr)/sizeof(arr[0]);

cout << "largest sum of contiguous sub-array is " << kadane(arr, n);

return 0;

}