CareerCup

Here is my answer to this question:

basicalgos.blogspot.com/2012/05/52-find-sub-array-of-max-sum.html

public static void printMaxSum(int[] a) {
		if (a == null || a.length == 0) return;
		int len = a.length;
		int max=a[0], maxi=0, maxj=0;
		int sum=a[0], i=0;
		
		for (int j=1; j<len; j++) {
			if (sum <= 0 || sum + a[j] <= 0) {
				sum = a[j];
				i = j;
			} else {
				sum += a[j];
			}
			if (sum > max) {
				max = sum;
				maxi = i;
				maxj = j;
			}
		}
		System.out.println("\nmaxi, maxj, and max are: " + maxi + "," + maxj + "," + max);
	}


O(n)

Thats right. A simple way to visualize this is to plot a curve of the recurring sum and take the starting and ending values as range values and the value of the peak as the sum.

my solution is using DP by filling the matrix with the sum values. The matrix column is i, the matrix row is j. First fill cells (i,i) with the values from the input array: M[i,i] = input[i]; Then fill the left side of matrix diagonal starting from [n-1, n-2] cell by using previously calculated values, i.e. M[7, 6] = M[7,7] + M[6,6]; M[7,5] = M[7,6] + M [5,5], etc. Finally find the max element in matrix. If no additional data structures are allowed then just go through array and calculate the value for each interval.

DP
public static void findStartAndEnd(int [] array){
int [] state=new int [array.length];
state[0]=array[0];
int max=state[0];
int start=0;
int end=0;

for (int i=1;i<array.length;++i){
if (state[i-1]+array[i]<=0){
state[i]=0;
start=i+1;
}else{
state[i]=state[i-1]+array[i];
if (state[i]>max){
max=state[i];
end=i;
}
}
}

System.out.println("SUM: "+max);
System.out.println("START: "+start);
System.out.println("END: "+end);
}

dp below is an array of state

struct state {
    int S, E, maxval;
};

This is the routine that will populate the dp array with max-sum starting from i (to j)

FOR(i, 1, n) {
    if (a[i] > 0) {
        RFOR(j, i-1, 0) {
            if (dp[j+1].maxval > 0) {
                dp[j].maxval = a[j] + dp[j+1].maxval;
                dp[j].E = i;
            } else {
                break;  // do not proceed further
            }
        }
    }
}

To get the max-state run over the dp and output the results. O(n^2)

Using Kdane's algorithm it can be done in O(n) and O(k) space.

func(int[] a) {
int startIndex=-1,endIndex=-1,maxEndingHere=0,maxSoFar=0;
int tempStartIndex=-1,tempEndIndex=-1;
for (int i=0;i<a.length;i++) {
//finding the maximum sum of all arrays that end at i
if (a[i] >= maxEndingHere+a[i]) {
tempStartIndex=tempEndIndex=i;
maxEndingHere = a[i];
} else {
tempEndIndex=i;
maxEndingHere = maxEndingHere+a[i];
}
//The maximum sum so far will be the sum of all the subarrays considered so far or all the
// sub arrays ending at this position.

if (maxEndingHere >= maxSoFar) {
startIndex = tempStartIndex;
endIndex = tempEndIndex;
maxSoFar = maxEndingHere;
}
}
return startIndex,endIndex;
}

#include<stdio.h>
int main()
{
int a[10]={3,2,-3,1,-10,-15,12,-3,11,12};
int sum=0,start,end;
int maxsum=0;
int i,j;
for(i=0;i<10;i++)
{
sum=0;
for(j=i;j<10;j++)
{
sum = a[j] + sum;
if(sum>maxsum)
{
	maxsum=sum;
	start = i;
	end = j;
}}
}
printf("%d\n",maxsum);
printf("start = %d , end = %d \n" ,start,end);
return 0;
}

#include<stdio.h>
#include<conio.h>
#define ub 7
int main()
{
int a[]={1,3,8,2,-1,10,-2,1};
int temp=a[1],highestindex,sum,lindex,index,uindex;
for(int i=0;i<=ub;i++)
        if(temp<a[i])
        highestindex=i;
printf("highest elemnt is %d",a[highestindex]);

temp=0;
sum=0;

index=lindex=highestindex;
while(index>0)
{
index--;
sum=sum+a[index];
if(sum>temp)
{
            temp=sum;
            lindex=index;
            printf("lindex %d\n",lindex);
}                

}
printf(" lb is %d  ",a[lindex]);


temp=0;
sum=0;

index=uindex=highestindex;
while(index<ub)
{
index++;
sum=sum+a[index];
if(sum>temp)
{
            temp=sum;
            uindex=index;
}                
}
printf(" ub is %d",a[uindex]);

getch();
}

#include<stdio.h>
#include<conio.h>
struct ret
{
 int lindex;
 int rindex;
 int sum;
};
struct ret find_max_cross_array( int arr[],int low, int mid ,int high);
struct ret find_max_subarray( int arr[],int low,int high);

int main()
{
  int arr[10]={20,12,-10,8,-61,-8,-5,4,26,-2};
  struct ret h;
  h=find_max_subarray(arr,0,9);
  printf("%d %d %d ",h. lindex,h.rindex,h.sum);
  getch();
}
struct ret find_max_subarray( int arr[],int low,int high)
{
  int cross_sum,cross_lindex,cross_rindex,right_sum,left_sum,left_lindex,left_rindex,right_lindex,right_rindex,mid;
  if(low==high)
  {
    struct ret b;
    b.lindex=low;
    b.rindex=high;
    b.sum=arr[low];
    return(b);
    //return(low,high,arr[low]);
  }
  else
  {
     struct ret c;
     mid=(low+high)/2;
     c=find_max_subarray(arr,low,mid);/////////////////
     left_lindex=c.lindex;
     left_rindex=c.rindex;
     left_sum=c.sum;
     c=find_max_subarray(arr,mid+1,high);//////////////
     right_lindex=c.lindex;
     right_rindex=c.rindex;
     right_sum=c.sum;
     c=find_max_cross_array(arr,low,mid,high);/////////
     cross_lindex=c.lindex;
     cross_rindex=c.rindex;
     cross_sum=c.sum;
     if(left_sum>right_sum)
     {
     right_sum=left_sum;
     right_lindex=left_lindex;
     right_rindex=left_rindex;
     }
     if(cross_sum>right_sum)
     {
     right_sum=cross_sum;
     right_lindex=cross_lindex;
     right_rindex=cross_rindex; 
     }
     c.lindex=right_lindex;
     c.rindex=right_rindex;
     c.sum=right_sum;
     return(c);     
  }
  
}
struct ret find_max_cross_array( int arr[],int low, int mid ,int high)
{
  struct ret a;
  int leftsum,j,rightsum,sum,maxleft,maxright;
  leftsum=-10000000;
  sum=0;
  for(j=mid;j>=0;j--)
  {
    sum=sum+arr[j];
    if(sum>leftsum)
    {
                   leftsum=sum;
                   maxleft=j;
    }
  }
  
  rightsum=-10000000;
  sum=0;
  for(j=mid+1;j<=high;j++)
  {
    sum=sum+arr[j];
    if(sum>rightsum)
    {
                   rightsum=sum;
                   maxright=j;
    }
  }
  a.lindex=maxleft;
  a.rindex=maxright;
  a.sum=leftsum+rightsum;
  return(a);
}