CareerCup

/*
	 * Returns a maximum sum value in an array of integers
	 */
	public int maxScan(int[] array)
	{
		if(array.length == 0) return -1;
		else if(array.length == 1) 
			return array[0];
		else
		{	
			int maxSum = array[0];
			int current_max = array[0];
			for(int i = 1; i < array.length; i++)
			{
				current_max = Math.max(array[i], current_max + array[i]); 
				maxSum = Math.max(maxSum, current_max);
			}
			return maxSum;
		}
	}

search Maximum_subarray_problem in wikipedia

Can you give some examples, I can't understand the problem?

Answered many times before on this site.

int main(){

int array[] = {80,18,-56453,53,14};

int n = sizeof(array)/sizeof(int);

int max_sum=0;
int sum=0;

for(int i = 0; i < n; i++)
{
if (sum+array[i]>=max_sum) {sum=sum+array[i]; max_sum=sum;}
else sum=0;
}

cout<< max_sum;

}

Can anybody tell me if all numbers are negative then how can we solve this problem.

#include<iostream>
using namespace std;
#include<stdio.h>
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;
if(max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}

/*Driver program to test maxSubArraySum*/
int main()
{
int a[] = {-2, 10,-13, 4, 7, -6, 1, 5, -3};
int max_sum = maxSubArraySum(a, 8);
printf("Maximum contiguous sum is %d\n", max_sum);
return 0;
}

#include<stdio.h>
#include<conio.h>
int max(int a[],int size){
int maxso.maxend=0,i;
for(i=0i<size;i++)
{if(maxend<0)
maxend=0;
}if(maxso<maxend){
maxso=maxend;}return maxso;}
int main(){
int a[]={1,2,3,4,5,6,-7,-7}
int maxsum=max(a,8);
printf("Sum %d",maxsum);getchar();
return 0;


}


}

int maxSumInSubArr(int array[], int size, int *startI, int *stopI)
{
int max_here, max_far;
max_far = INT_MIN;
max_here = 0;
int tmpStart = *startI;

for (int i=0; i < size; i++) {
max_here = max_here + array[i];
if(array[i] > max_here)
{
max_here = array[i];
tmpStart = i;
}
if(max_here > max_far)
{
max_far = max_here;
*stopI = i;
*startI = tmpStart;
}
}
return max_far;
}

onestopinterviewprep.blogspot.com/2014/03/namespace-arrayproblem-write-function.html

I have written this code. I have taken the size of the array to be 20. You change it according to your need.

#include<iostream>
using namespace std;
int maxcross(int arr[],int low,int mid,int high){
	int left_sum = -1,sum=0,max_left,right_sum=-1,;
	for(int i=mid;i>=low;i--){
		sum+=arr[i];
		if(sum>left_sum){
			left_sum=sum;
			max_left = i;
		}
	}
	sum=0;
	for(int i=mid+1;i<=high;i++){
		sum+=arr[i];
		if(sum>right_sum){
			right_sum = sum;
		}
	}
	return left_sum+right_sum;
	
}
int max_sub_array(int arr[],int low,int high){
	if(high==low)
		return arr[low];
	else{
		int mid = (low+high)/2;
		int left_sum = max_sub_array(arr,low,mid);
		int right_sum = max_sub_array(arr,mid+1,high);
		int cross_sum = maxcross(arr,low,mid,high);
		if(left_sum>right_sum&&left_sum>cross_sum)
			return left_sum;
		else if(right_sum>cross_sum)
			return right_sum;
		else
			return cross_sum;
		
	}
}


int main(){
	int arr[20];
	cout<<"Enter the size of the array(max 20):\n";
	int n;cin>>n;
	cout<<"Enter the array:\n";
	for(int i=0;i<n;i++)
		cin>>arr[i];
	int ans = max_sub_array(arr,0,n-1);
	cout<<"The Maximum sum is: "<<ans<<endl;
	
	
	return 0;
}

Have any queries. Please comment

int maxSubArray(vector<int> A) {
	int start = A[0];
	int sum = A[0];
	int max = A[0];
	
	for(int i = 1; i < A.size(); i++) {
		sum += A[i];
		if(sum - start > max) {
			max = sum - start;
		}
		if(sum < start) {
			start = sum;
		}
	}
	return max;
}

public int getMaximumSum(int[] inputs){
int sum = 0;
for(int i=0; i<inputs.length;i++){
if(sum + inputs[i] > sum){
sum = sum + inputs[i];
}
}
return sum;
}

///
public int getMaximumSum(int[] inputs){
int sum = 0;
for(int i=0; i<inputs.length;i++){
if(sum + inputs[i] > sum){
sum = sum + inputs[i];
}
}
return sum;
}
///

public int getMaximumSum(int[] inputs){
        int sum = 0;
        for(int i=0; i<inputs.length;i++){
           if(sum + inputs[i] > sum){
                sum = sum + inputs[i];
           }
        }
        return sum;
    }

package amazonExcerise;

import java.util.Arrays;
import java.util.Collections;

public class TestNGValidation {
public static void main(String[] args) {
int a[]={-1, -11, -2, 3, -5, 10, -1, 3, 2, 1};
int[] b = new int[500];
int k=0,Result=0;
for(int i=0;i<=a.length-1;i++){
	Result=0;
	for(int j=i;j<=a.length-1;j++,k++){
		Result=a[j]+Result;
		b[k]=Result;
	}
}
Arrays.sort(b);
System.out.println("The maximum sum possible from different sub Arrays : "+b[b.length-1]);
	
}
}

Working code

int main(){

int array[] = {18,-18, -53, 53, 4};

int n = sizeof(array)/sizeof(int);

printf("\n Length-- %d --i \n",n);
int max_sum=0;
int sum=0;

for(int i = 0; i <= n; i++) {

sum+=array[i];

if(sum>max_sum){
max_sum=sum;}
else if (sum < 0) {
sum = 0;
}

}

printf("\n -> %d \n",max_sum);

}
~