CareerCup

Supose S is the array of integers, N the length and sum the current sum.
Let best be the solution at current step.We keep in x and y the limit of the best array
Initally,best = -INF and sum = 0.
Then

for(i = 0 ;i < N ; ++i)
  {
   if(sum <= 0) {sum = S[i] ; idx = i; } 
   else sum += S[i];
   if(best < sum) {best = sum;x = idx ; y = i;}

The solution will be the subarray [x,y]. Complexity O(N) time O(1) memory and one loop.

#include <iostream>
using namespace std;
int main()
{
    int max_so_far = 0,max_ending_here =0;
    int A[] = {14,-15,6,-3,2,3,4,5,-1};
    int numOfLoops = 0;
    int size = sizeof(A)/sizeof(int);
    for(int i=0;i<size;i++){
	++numOfLoops;
        max_ending_here = (max_ending_here + A[i])>0?max_ending_here + A[i]:0;
        max_so_far = max_ending_here>max_so_far?max_ending_here:max_so_far;
    }
    cout<<"number of loopings:"<<numOfLoops<<endl;
    cout<<"Maximum sum::"<<max_so_far<<endl;
}

I can't believe interviewers still actually ask this question....

After trying out this question, it looks so simple to write the code for that.

int main()
{
	int arr[]={14,-15,6,-3,2,3,4,5,-1};
	int size = sizeof(arr)/sizeof(int);
	int i,maxsum=arr[0];
	for(i=1;i<size;i++)
	{
		maxsum = ( (maxsum+arr[i])<maxsum) ? ( maxsum>arr[i] ? maxsum:arr[i] ) : (maxsum+arr[i]) ;
	}
	printf("Maximum sum:%d",maxsum);
}

public static int FindMaxLength(int []inputArray)
{
int prevValue=inputArray[0];
int sum=0;
for(int i=1;i<inputArray.Length;i++)
{
if((sum+inputArray[i])>inputArray[i])
sum+=inputArray[i];
else
sum=inputArray[i];
}
return sum;
}

ideone.com/WmT0k

Void findSubArray(int[] array){
int best=0;
int worst=0;
int worstIndex=0;
int start=0;
int end=0;
int sum=0;
for (int i=0; i<array.length;i++){
sum+=array[i];
if((sum-worst)>best){
start=worstIndex;
end=i;
best=sum-worst;
}
if(sum<worst){
worstIndex=i;
worst=sum;
}
}
}

int GetMaxSubArray(int[] Numbers, out int start, out int end)
        {
            int sum = 0;
            int maxsum = int.MinValue;
            start = 0;
            end = 0;

            for (int i = 0, j = 0; j < Numbers.Length; j++)
            {
                sum += Numbers[j];
                if (sum > maxsum)
                {
                    maxsum = sum;
                    start = i;
                    end = j;
                }

                if (sum < 0)
                {
                    sum = 0;
                    i = j + 1;
                }
            }

            return maxsum;
        }

public class MaxSubArray {
	
	public static void main(String[] args){
		
		int[] arr = new int[]{-2,4,-3,6,8,-3,2,-4,-1};
		MaxSubArray max = new MaxSubArray();
		max.subArray(arr);
	}

	public int subArray(int[] array){
		int maxsum =0;
		int sum =0;
	        int start=0;
	        int end=0;
		
		for(int i=0; i<array.length; i++){
			sum = sum + array[i];
			if(maxsum < sum){
				maxsum=sum;
				end=i;
			}
			if(sum<0){
				start=i+1;
				sum=0;
			}
		}
		System.out.println("SUM: "+maxsum+", Start Index: "+start+", End Index: "+end);
		return maxsum;
	}
}

THIS ONE IS SIMPLE AND BEST OF ALL ALTHOUGH ITS NOT MY CODE

sum and maxsum = 0;

for i=0 to i<n
sum += a[i];
if(sum<0)
sum = 0;
else if(maxsum < sum)
sum = maxsum;

public static int findMaxSub(int [] input ){
		int max=Integer.MIN_VALUE;
		int current=0;
		for(int i=0;i<input.length;i++){
			current+=input[i];
			if(current>max)
				max=current;
			if(current<=0)
				current=0;
		}
		return max;
	}

this code should work.

all of you are retarded