The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Arrays & Strings

Problem :-
Find the largest sum contiguous subarray.
Given an array of positive and negative integers, find a contiguous subarray whose sum (sum of elements) is maximum. We are interested only in the maximum sum.
For e.g, Consider the array { 2,-4, 3, -2, 6, -9, 5 } .
Largest sum contiguous subarray is { 3, -2, 6 } & the sum is 7.
There is no other contiguous subarray with sum > 7.

Solution :-
Maintain two variables prev_max and curr_max, both initialized to 0.
Update prev_max & curr_max as you iterate over the array.
For i = 0 ... n-1, curr_max = curr_max + 1, if arr(i) is positive & curr_max = 0, if arr(i) is negative.
Update prev_max whenever curr_max > prev_max.
See the implementation below.

#include<iostream>
using namespace std;

// find the largest sum of contiguous subarray elements 
int findLargetSumSubarray(int arr[],int size) {
   int prev_max = 0; // max sum so far
   int curr_max = 0; // curr_max
   int i;
   int j=0,k=0;
   for (i=0;i<size;i++) {
      curr_max += arr[i];
      if (curr_max < 0) {
         // if sum becomes (-)ve, change it to zero
         curr_max = 0;
      }
      else if (prev_max < curr_max) {
         // if sum becomes greater than the max sum 
         // so far update it
         prev_max = curr_max;
      }
   }
   return prev_max;
}

// main
int main() {
   int arr[] = { 1,4,-6,6,-4,7,1,3,-2,1 };
   int size = sizeof(arr)/sizeof(arr[0]);
   int largest_sum = findLargetSumSubarray(arr,size);
   cout<<"\nLargest :: "<<largest_sum;
   cout<<endl;
   return 0;
}

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j - i ) s.t arr(j) > arr(i)