CareerCup

int maxsum(int arr[], int arraylength, int & startIndex, int & endIndex )
{
	int maxsum = arr[0], sum = arr[0];
	startIndex = 0,endIndex = 0;
	int tempstIndex = 0, tempendIndex = 0;

	for(int index =1 ;index < arraylength;index++)
	{
		if(sum < 0)
		{
			sum = arr[index];
			tempstIndex = tempendIndex = index;
		}else{
			sum = sum + arr[index];
			tempendIndex = index;
		}

                if(maxsum < sum)
		{
			maxsum = sum;
			startIndex = tempstIndex;
			endIndex = tempendIndex;
		}
	}
	return maxsum;
}

int maxSum = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < inputList.Length - 1; i++)
{
int tempSum = inputList[i] ;
for (int j = i + 1; j < inputList.Length; j++)
{
tempSum += inputList[j];
if (tempSum > maxSum)
{
maxSum = tempSum;
startIndex = i;
endIndex = j;
}
}
}

Maximum Sum Subarray Problem

Kadane's algorithm...

public static int getMax(int[] arr){
        int maxsum=0;
        int sum=0;
        for(int i=0;i<arr.length;i++){
            sum+=arr[i];
            if(maxsum < sum)
                   maxsum=sum;
            else if(sum<0)
                sum=0;
        }
        return maxsum;
    }

Note:It will not work if array has all negative values.

incase of all negative numbers, the maxsum will be negative. At that time, find the greatest number in the array which indicates the maximum sum.

Source code : Time complexity = O(n), Space complexity = O(1)

void find_max_sum(int *arr, int n, int *start, int *end, int *sum)
{
	int i, temp_sum, temp_start, temp_end; 

	*end = *start = temp_start = temp_end = -1;
	*sum = temp_sum = 0;

	for(i = 0; i < n; i++)
	{
		temp_sum += arr[i];

		if(temp_sum < 0)
		{
			temp_sum = 0;
			temp_start = temp_end = -1;
		}
		else if(temp_sum > 0)
		{
			if(temp_start == -1)
				temp_start = i;
			temp_end = i;
		}

		if(temp_sum > *sum)
		{
			*start = temp_start;
			*end = temp_end;
			*sum = temp_sum;
		}
	}
}

double maxSubarray(double a[], int numElements)
{
double max=0;
double here=0;
int i;

for(i = 0; i < numElements; i++)
{
here = (here + a[i] > 0) ? here + a[i] : 0;
max = (here > max) ? here : max;
}
return max;
}

Its just Kadane's algo...Java implementation would go like this

public static void implementAlgo(int[] pArray) {
		int max_so_far = 0;
        int max_ending_here = 0;
        int maxStart=0;
        int maxEnd=0;
        int currentStart=0;
        for(int i=0;i<pArray.length;i++){
        	max_ending_here=max_ending_here+pArray[i];
        	if(max_ending_here<0){
        		max_ending_here=0;
        		currentStart=i+1;
        	}
        	if(max_so_far<max_ending_here){
        		max_so_far=max_ending_here;
        		maxStart=currentStart;
        		maxEnd=i;
        	}
        }
        System.out.println("Max="+max_so_far);
        System.out.println("Started from:"+maxStart);
        System.out.println("Ended at :"+maxEnd);
	}