CareerCup

Use Kadane's algorithm

int[] x = { -2, 4, 2, 3, -12, 5, 9, -8, 9 };

		int max = x[0];
		int sum = max;

		for (int i = 1; i < x.length; i++) {

			sum = sum + x[i] > x[i] ? sum + x[i] : x[i];

			if (sum > max)
				max = sum;
		}
		System.out.println(max);

What about this variation (in C++) of Kadane's algorithm, usefull for positive or negative numbers?

#include <iostream>

int calculateSum(int* a, size_t len)
{
  int sum =a[0]+a[1], aux=a[0];
  for (int i=1;i<len;++i)
  {
    aux=aux+a[i];
    if (aux>sum)
      sum=aux;
    aux=a[i];
  }
  return sum;
}

int main()
{
  int a[] = {-10, -12, -7, -5, -4, -13};
   std::cout<<"Sum = "<<calculateSum(a, sizeof(a)/sizeof(a[0]))<<std::endl;
}

P.S.: I understood consecutive as adjacent, so I guess it isn't valid.

My implementation in C++ of the Kadane's algorithm:

#include <iostream>
#include <limits>

long calculateSum(int* a, size_t len)
{
  long maxSum(std::numeric_limits<long>::min()), currentMaxSum(0);
  int maxStartIndex(0), maxEndIndex(0), currentStartIndex(0);

  for (int currentEndIndex=0; currentEndIndex<len; ++currentEndIndex)
  {
    currentMaxSum = currentMaxSum + a[currentEndIndex];
    if (currentMaxSum > maxSum)
    {
      maxSum = currentMaxSum;
      maxStartIndex = currentStartIndex;
      maxEndIndex = currentEndIndex;
    }
    if (currentMaxSum < 0)
    {
      currentMaxSum = 0;
      currentStartIndex = currentEndIndex + 1;
    }
  }
  return(maxSum);
}

int main()
{
  int a[] = {-2, 4, 2, 3, -12, 5, 9, -3, 4};
  std::cout<<"Sum = "<<calculateSum(a, sizeof(a)/sizeof(a[0]))<<std::endl;
}

//Kadane's Algorithm
void findMaxSum(int *arr, int len)
{
int i,local_max=0,max=0;
local_max=arr[0];
for(i=1; i<len; i++)
{
local_max = (local_max+arr[i]>0) ? local_max+arr[i] : 0;
max= local_max>max? local_max: max;
}

printf("sum is %d\n",max);

}

This is maximum sub-array problem...use the divide & conquer method.
recursively divide the array into two sub-parts left & right.
find max left sum.max right sum & max cross sum whichever is greater return that.

Algorithm:
function(A,low,high)
{
mid=(low+high)/2
(left-low,left-high,left-sum)=function(A,low,mid);
(right-low,right-high,right-sum)=function(A,mid+1,high);
cross-low,cross-high,cross-sum=find max-crossing subarray(A,low,mid,high)
if(leftsum>=rightsum && leftsum>=cross-sum)
return (left-low,left-high,left-sum);
else if (leftsum<=rightsum && rightsum>=cross-sum)
return (right-low,right-high,right-sum);
else
return (cross-low,cross-high,cross-sum);
}

find-cross-subarray(A,low,mid,high)
{
find left max sum from i=mid to low & store that cross-low=i
find right max-sum from i=mid+1 to high & store that cross-high=i ;

return (cross-low,cross-high,left-sum+right-sum)
}

Time complexiety: O( n logn )

this problem can be solved by using a stack and array location of size n.......and maitain two sum counter.....one for stack element sum and one for array element sum
steps---------->
1. intialize the sum_array= minusinfinite and sum_stack=0;

while(last element not reached) do step 2 to 4

2. read element from given input push the content to the stack and add the its value to sum_stack; sum_array +=input[s[top][;

3. now compare sum_array and sum_stack
3.1 if(sum_stack>sum_array) then copy down stack content to array;
3.2 else no change in array;
4. now check is adding element to sum_attack makes it -ve or not
if yes then pop all the elmenet from stack; i.e top=0;


5.finally what left in array is index of input array whose element sum is max

#include<iostream>

using namespace std;

int main()
{
int a[50],i,j,k,n,sum1=0,sum2=0,tempsum=0;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i];
}

for(i=1;i<=n;i++)
{
for(j=0;j<=n-i;j++)
{
for(k=j;k<j+i;k++)
{
tempsum=tempsum+a[k];
}
if(sum2<tempsum)
sum2=tempsum;
tempsum=0;
}
if(sum1<sum2)
sum1=sum2;
}

cout<<"Maximum sum : " <<sum1;
return 0;
}

int FindSum(int arr[], int n)
{
int sum = 0;
int cSum = 0;

for(int i = 0; i<n; i++)
{
if(arr[i]>0)
{
if(cSum < 0)
cSum = arr[i];
else
cSum += arr[i];

}
else
{
if(cSum < arr[i])
{
cSum = arr[i];
}
else
{
cSum += arr[i];
}
}
if(cSum>sum)
{
sum = cSum;
}
}
return sum
}

main()
{
max_sum = a[0]; <- Current maximum value.. assign as first element.
max_right = 0; <- Cur right/left maintain interval for the current maximum sum
max_left = 0;

right = 0; <- these 2 are potentially moving as we go along;
left = 1;
sum = A[0]; <- Moving sum;

for (left = 1; left < n; left++)
{
sum = sum + a[left];
if ((sum) > max_sum)
{
max_left = left;
max_right = right;
max_sum = sum;
}
else if (cur_sum < 0)
{
right = left + 1;
}
}

printf("MAX SUM = %d\n right = %d left = %d\n",
max_sum, max_right, max_left);
}

public static void MaximumSumSubarray(int[] SourceArray)
{
int baseStart, baseEnd, baseSum;
int localStart, localEnd, localSum;

localStart = localEnd = localSum = 0;
baseStart = baseEnd = baseSum = 0;

Console.WriteLine("Source Array: ");
for (int i = 0; i < SourceArray.Length; i++)
{
Console.WriteLine("{0}: {1}", i, SourceArray[i]);
if (SourceArray[i] > 0 && localStart == 0)
{
localStart = i;
localSum = SourceArray[i];
}
else
{
localSum += SourceArray[i];
}

if ((i == SourceArray.Length - 1) || (SourceArray[i + 1] < 0 && localStart != 0))
{
localEnd = i;
if (localSum > baseSum)
{
baseSum = localSum;
baseStart = localStart;
baseEnd = localEnd;
}
localStart = localEnd = localSum = 0;
}
}

Console.WriteLine("Maximum sum subarray: Start:{0} End:{1} Sum:{2}", baseStart, baseEnd, baseSum);
Console.ReadLine();
}

@sachinism - I need some help regarding this. Can ypu pls add me on prashantgupta509@gmail.com

Since i am a beginner i wont be focusing on the complexities, this algorithm is very easy though having a terrible complexity of O(n^3):

let there be N digits stored in an array A :
max = max sum value
w = window size
n = number of elements
t= local variable

max = 0
for w = n to 1
for t = 1 to n-w+1
for i = t to t+w-1
*sum the elements of the array*
if max < sum
{ max = sum
b=t
c= t+w-1 // store the index values }
make a dry run on an array of five elements! it works!

int maxSubArraySum(int a[], int size)
{
   int max_so_far = 0, max_ending_here = 0;
   int i;
   for(i = 0; i < size; i++)
   {
     max_ending_here = max_ending_here + a[i];
     if(max_ending_here < 0)
         max_ending_here = 0;
 
     /* Do not compare for all elements. Compare only   
        when  max_ending_here > 0 */
     else if (max_so_far < max_ending_here)
         max_so_far = max_ending_here;
   }
   return max_so_far;
}

private static void FindLargestSum()
        {
            var srcList = new List<int>() { -2,4,2,3,-12,5,9,-3,4 };
            var diffList = new List<int>();
            int Sum = 0;
            int maxIdx = 0;
            int i = 0;

            //Calculate total Sum
            foreach (int el in srcList)
                Sum += el;

            //Find differential sums
            for (i = 0; i < srcList.Count; i++ )
            {
                Sum -= srcList[i];
                diffList.Add(Sum);
            }

            //Find max differential and identify the indexes for the largest sum
            Sum = 0;
            for (i = 0; i < diffList.Count; i++)
            {
                if (diffList[i] > Sum)
                {
                    Sum = diffList[i];
                    maxIdx = i;
                }
                
            }

            Console.WriteLine("Max Sum = " + Sum.ToString());
            Console.WriteLine(string.Format("Consecutive Indexes: {0} - {1}", (maxIdx + 1).ToString(), (srcList.Count - 1).ToString()));
        }

find sum of upto index list
for given list = [-2 4 2 3 -12 5 9 -3 4 ]
Sum upto Index List = [-2 2 6 9 -3 2 11 8 12]

now find MAX ( SumArray[i+] - Array[i] ) for all combinations....
and SumArray[8] - SumArray[5] == (12) - (-3) = 15