Maximum Sub-Array Sum : Kadane's Algorithm

Originally Posted on SeedBx

Array is almost, in some way, in every application of programming and computer science in general. With array being so important in practical application any procedure on array becomes significant.

In this post we will look at the problem of finding maximum sub-array sum which can be done efficiently by using Kadane's Algorithm.

Problem Statement

Given an array of elements A, find the maximum sub-array sum.

Note : Sub-array is a collection or block of contiguous items in an array.

Example : For array A[]={1, 2, 3, 4}, {1, 2} is a sub-array whereas {1, 3} is not.

Naive Approach

Loosely speaking, we can traverse each and every subset that can be generated and calculate the sum for each and every possible subset.

Pseudo Code :

maxsum=0

for i=0 upto A.length

    sum=0

    for j=i+1 upto A.length

        sum=sum+A[j]

        if(sum>maxsum)

            maxsum=sum

 

Time Complexity : O(|A|²)

Space Complexity : O(|A|)

 

Kadane's Algorithm

The approach of Kadane's Algorithm is simple. We keep two flags, namely maxSum and currSum which store the global maximum and the local maximum respectively.

At each iteration we update the currSum as the maximum of currSum+currElement and currElement.

·       If currSum + currElement is bigger then, we are adding to a sub-array started at a position before the currElement's position.

·       If currElement is bigger then, we are considering the sub-array that is starting at the currElement's position.

At each iteration, we also update the maxSum by checking if the local maximum is the global maximum i.e. we update maxSum to be the maximum of maxSum and currSum.

Example : Let us consider an array A[]={12, 23, -38, 1, 2}.

• We initialise maxSum, currSum with the value at A[0].

• At index 1, we update the value of currSum=max(12, 12+23)=35 and maxSum=max(12, 35).

• At index 2, we update the value of currSum=max((-38), 35+(-38))=-3 whereas the value of maxSum remains unchanged.

• At index 3, we update the value of currSum=max(1, 1+(-3))=1 and the value of maxSum remains unchanged.

• At index 4, we update the value of currSum=max(2, 2+1)=3 and the value of maxSum remains unchanged.

Hence, the maximum sub-array sum for this array A is maxSum=35.

Pseudo Code :

maxSum=currSum=A[0]

 

for i=1 upto A.length

    currSum=max(A[i], currSum+A[i])

    maxSum=max(maxSum, currSum)

 

Time Complexity : O(|A|)

Space Complexity : O(|A|)

 

Kadane's Algorithm is one simple algorithm that in a very few lines of code finds the maximum sub-array sum of an array. This algorithm can be applied for business analysis to study sales, profits and losses so as to make judicial business decisions.

Thanks for reading.

 

Gentle Introduction to C : Array

Originally Posted on SeedBx 

Welcome to the ninth part of the Gentle Introduction to C series. As said before this series aims to provide you a brief introduction to C language.

In this post, we will learn about a very basic data structure, namely single-dimensional array, often just called array.

Interesting Fact : Array is at the base of computer memory. Computer memory is just a very big array.

Array

Array is a collection of similar objects or items which are stored in a contiguous fashion.

Let us understand this definition by breaking it into two parts.

Collection of Similar Items

Array can be used to store almost any data type. However given the data type, we cannot store data items of any other kind in it.

Example :

The above array is valid and is an example of an int type array.

However, the above array is invalid because the array contains more than one type, namely char, float and int.

Stored in Contiguous Manner

Array elements, in the computer memory, are stored in contiguous memory locations. Hence by knowing the memory address of any of the elements of an array, we can reach to any other array element by just traversing the memory addresses in a linear fashion.

Note : Array elements in C (and most of the programming languages) can be accessed using their index. Indexes are like placeholder which can be used to get information or value at any position in the array. In C, 0-based indexing is used i.e. the first element is at the 0^th index position.

Example :

Declaring an Array

An array in C can be declared in three different ways.

1.    Declaration by Specifying Size

  datatype arr_name[size];

2.    Declaration by Initialising Array

  datatype arr_name[]={items, in, a, comma, seperated, list};

3.    Declaration by Specifying Size and Initialising Array

  datatype arr_name[size]={size, items, in, a, comma, seperated, list};

For example,

int a[10];

char name[]={'a', 'a', 'y', 'u', 's', 'h'};

char foo[6]={'r', 'a', 'n', 'd', 'o','m'};

In the above code snippet, three arrays have been declared one, a, of int type of size 10 and the others, name and foo, of char type and size 6.

Note : An array declaration like,

char bar[1]={'m', 'o', 'h', 'a', 'n'};

will not give a compiler error and rather will just give a warning. However this declaration is not encouraged.

Accessing Array Elements

As said above, array elements can be accessed using indexes. In C (and many similar programming languages), indexes start at 0 and are always positive.

To access the n^th element in an array arr_name we will write the array name followed by the index in square brackets i.e.

     arr_name[n-1]

For example, in the above given array name, if we want to access the first char, we can do so by

    name[0];

Note :

     arr[-1];

arr[100];

In C, there is no index out of bound checking i.e. if for a given array, arr of size 10, the above code snippet will not give any error, however the results returned will be unexpected and totally garbage.

Array is a data structure that is not only limited to C and rather is fundamental to almost all programming languages. There are some flaws in array, particularly it's static nature, which are overcame in many other array-like data structures. However array is often the starting point for many applications.

There is still much to be said about arrays, in particular of it's other variant i.e. multi-dimensional array but I will leave that for another post.

Thanks for reading.

Also See : Function, Pointers