CareerCup

int largest(int[] arr){
	int sum= 0;
	int tempsum=arr[0];
	for(int i=1;i<arr.length();i++){
		if(arr[i]>0)
			tempsum+=arr[i];
		else
			tempsum=arr[i];
		if(tempsum>sum)
				sum=tempsum;

	}
	return sum;
}

Sorry --- the above code doesn't work if the input is {2,-8,3,-2,4}
here the output is 5 {3,-1,4}

Here is the modified solution

int largest(int[] arr){
	int sum= arr[0];
	int tempsum=arr[0];
	for(int i=1;i<arr.length();i++){
		tempsum+=arr[i];
		if(tempsum>sum)
			sum=tempsum;
		if(tempsum<0)
			tempsum=0;
	}
	return sum;
}

Sorry for the confusion
Here is the correct code

int largest(int[] arr){
	int sum= arr[0];
	int tempsum=0;
	for(int i=0;i<arr.length();i++){
		tempsum+=arr[i];
		if(tempsum>sum)
			sum=tempsum;
		if(tempsum<0)
			tempsum=0;
	}
	return sum;
}

This is wrong. For inputs 5, 3. You algorithm outputs sum as 8 while the correct answer is 5.

#include<stdio.h>

void
print_max_sum(int *a, unsigned int length)
{
unsigned int end = 0;
unsigned int i = 0;
unsigned int start = 0;

int is_frozen = 0;
int cur_sum = 0;

for (; i < length; i++) {

if (a[i] + cur_sum > cur_sum) {

if (is_frozen) {
start = i;
end = i;
is_frozen = 0;
} else {
end = i;
}
cur_sum = a[i] + cur_sum;

} else if (is_frozen == 0) {
is_frozen = 1;
cur_sum = 0;
}
}
(void) printf("S = %d , E = %d\n", start, end);
}

int
main()
{
int a[] = {1, 2, -3, 4};
unsigned int length = sizeof(a) / sizeof(int);
print_max_sum(a, length);
return (0);
}

def max_subarr(arr):
    global_max_sum,local_max_sum,intervening_negative=0,0,0
    index=0
    while True:
        local_max_sum=max(0,local_max_sum+intervening_negative)
        
        while index!=len(arr) and arr[index]>=0:
            local_max_sum+=arr[index]
            index+=1
            
        global_max_sum=max(local_max_sum,global_max_sum) 
        
        if index==len(arr):
            if global_max_sum==0:
                global_max_sum=max(arr)
            return global_max_sum
        
        intervening_negative=0
        
        while index!=len(arr) and arr[index]<0:
            intervening_negative+=arr[index]
            index+=1
            
if __name__ == '__main__':
    print max_subarr(list(input("Enter elements: ")))

int largestsum(int a[], int len) {
int largest = a[0];
int tmp = a[0];
for(int i = 1; i < len; ++i) {
if(tmp + a[i] > a[i])
tmp+=a[i];
else
tmp = a[i];
if(tmp > largest)
largest = tmp;
}
return largest;
}