Search

Design and analysis techniques are important for becoming a good programmer

Man is curious being by nature. To quench his thirst of knowledge he makes discoveries, such discoveries which makes the answers easier. Similar is the fate of importance of algorithms.”

-By Kalindi Design and analysis of algorithm techniques are of supreme importance. Orientation in life as well as in technical aspects makes our life easier. Algorithms are building blocks for any problem which are solvable.

Writing programs and writing better programs are two different things. When we write programs, we just find a possible solution for it. But when we write programs using efficient algorithms, we reduce computational power and make the program better for the real-life problems in industries. Situational Example:

Ram is having exam of English tomorrow; he is unable to find out the meaning of a particular word. He refers to an online dictionary (unsorted, i.e., all the words are distributed unevenly not ordered according to alphabetical order) using naïve technology he has to turn each page to find out the correct word he was searching for. This will make him lose all his energy on finding that particular word and will waste his precious time.

His friend Shyam comes and applies the concept of bubble sort which helps ram to find the word immediately and now he can study for his exam again and prepare on time. This is the boon of design and analysis techniques of algorithms, which has made the life of everyone easier. We may not realise it every now and then but its present everywhere.

Let us discuss the problem statement.

Given an array of integers, our motive is to find the sum of contiguous

subarray of numbers having the largest sum.

Note: The subarrays are continuous i.e., elements cannot be skipped in between

and needs to be picked in a continuous fashion without any breaks in between. If all the elements are positive, then the subarray would be the

entire array itself. However, the problem gets interesting when some

negative elements are there in between.

Let us go through the below problem statement and analyse how a small modification which I made in the below algorithm saved 990K iterations and how it was useful.

Consider an array

Input: [-2,1, -3,4, -1,2,1, -5,4]

Output: 6

Explanation: It will have the largest sum when the subarray [4, -1,2,1] is

considered, which will return the sum {4+(-1) +2+1} = 6.

Let us now dive into the Brute force approach which is most commonly

used everywhere and try to implement the optimized version of the same:

Pseudocode of Naïve Brute Force:

void allSubarrays(int arr[], int n) {
pair<int, int> ind;
int max_sum = INT_MIN, cur_sum = 0;
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
cur_sum = 0;
//Elements of subarray(i, j)
for(int k = i; k <= j; k++) {
cur_sum += arr[k];
}
if(cur_sum > max_sum) {
max_sum = cur_sum;
ind = make_pair(i, j);}}}
cout << "Max sum : " << max_sum << endl;

Here, the inner-most loop is used to establish the sum of elements starting from index 'i' till index 'j'. A pair object has been used to store the indexes marking the starting and the ending index of the maximum sum subarray.

One can easily note that this particular inner loop is redundant as the sum of the subarray from index 'i' to 'j' can be calculated cumulatively in O(1) instead of creating a loop to calculate it independently in every iteration.