Choose jour language!

---

|

THE MAXIMUM SUM OF CONSECUTIVE SUBARRAY

Determine the maximum sum of all sub arrays from the observed sequence of numbers.
{ 3,5,-10,-34,16 2}

Problem to be solved: Determine the maximum sum of all consecutive subarrays from the observed array of numbers.
For an array A of n numbers, a continuous subarray A is another array consisting of either zero or more consecutive elements of array A.
In the previous example, e.g. array:
{5, -10, -34}
is continuous, while
{3, -34, 2}
it's not

---

Algorithm for determining the maximum sum of consecutive subarrays-video 

The video explains in detail through animation, the described algorithm that determines the maximum sum of subarrays for a given array. The algorithm starts from the definitions of problems and it is quadratic complexity.

---

Let's We notice all the arrays, in order to form sums from them and find the maximum​

{}, {3}, {3,5}, {3,5,-10}, {3,5,-10,-34,}, { 3,5,-10,-34,16 }, { 3,5,-10,-34,16 2}

{5}, {5,-10}, {5,-10,-34,}, { 5,-10,-34,16 }, { 5,-10,-34,16 2}

{-10}, {-10,-34,}, { -10,-34,16 }, { -10,-34,16 2}
​
etc.

​In order to change the starting positions, and then from a certain starting position go through the array, you will using the nested loop.
​All subarrays could be obtained using a loop in which for the current position of the initial element determined, we change the end position in order and print all members of the array from the initial to the final positions:

int A[ ]={ 3,5,-10,-34,16 2};
…

for(int end=st; end < n; end++)
{

for(int j=st; j<=kr; j++)
{

printf("%2d",A[j]);

}
printf("/n");

}

And now we would insert this code into the body of another for loop that changes the start from 0 to n.

for(int st=0; st <= n; st++)
{

for(int end=st; end < n; end++)
{

for(int j=st; j<=end; j++)
{

printf("%2d",A[j]);

}
printf("/n");

}

}

Since the sums of these subarray are calculated, and that is the largest sum, one of  the nested for loop can be avoided because the temporary sum of the current subarray is always remembered, so for the next element in the for loop whose yellow was nested, it is only added to the previous sum and then compare the sum with the current maximum.
So:

#include < stdio.h >
#include < stdlib.h >

int main()
{

const int n = 6;
int A[ ]={ 3,5,-10,-34,16 2};
int s=0;
int M=0;
for(int st=0; st < n; st++)
{

s=0;
for(int end=st; end < n; end++)
{

s=s+A[end];
if(s>M)

M=s;

}
printf("/n");

}
printf("M=%3d",M);

}

Special case 1: If all members of the array are positive

​In that case, it is obvious that the largest sum will be from the subarray with the most elements, and that is the array itself.

Special case 2: If all members of array are negative

In that case, it is obvious that the largest sum will be from the subarray with the least elements, and that is an empty array.

---

The task can also be solved by creating a function that determines the maximum of the subarray, for a given fixed starting position, and then the previously created function is called through the loop in the main function and the starting position and the starting array itself are sent as parameters, as well as the number of elements.

---

This algorithm is slow and quadratic of the  complexity. It should be noted that the inner loop passes through almost all elements of the array as in the previous cycle, only without the first member of the array, ie. add 1 element less in sum.
 For example. if in one iteration of the outer loop it passes through the following elements:

{3, 5, -10, -34,16, 2},

Then the following would go through:

{5, -10, -34,16, 2}.

Therefore, the sum in the second Iteration can be obtained as TheSumOfTheFirstIteration - 3.

​Through the outer loop, the initial values ​​that are used to pass through the nested one are actually moved, while the last value in the inner loop was fixed. We could reverse the task, ie. if we keep the beginning unchanged while we change the end value using the outer loop.
Then in each subsequent iteration we would have 1 element more to add. For example:
If you were to add elements in an iteration:

{3, 5, -10}

in the following they would add:

{3, 5, -10, -34}

We can conclude that the sum in the second iteration is the sum in the previous one increased by the last element:
SumAfterSomeIteration = SumInPreviousIteration + (- 34).

In this way, we came to Kadane's Algorithm for determining the maximum sum of contiguous subsequences.
​

Kadane's Algorithm

---

Previous
​|< The Euclidean algorithm

Next
​​​​​​​Basic data structures >|

---