[go: up one dir, main page]
Scribd
Upload
8 views1 page

Maximum Sub Array

The document discusses the problem of finding the contiguous subarray within an array that has the largest sum. It provides an example with the array [-2,1,-3,4,-1,2,1,-5,4], where the subarray [4,-1,2,1] yields the maximum sum of 6. Two implementations of the solution in Java are presented, demonstrating different approaches to calculate the maximum subarray sum.

Uploaded by

Vidyashankar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views1 page

Maximum Sub Array

The document discusses the problem of finding the contiguous subarray within an array that has the largest sum. It provides an example with the array [-2,1,-3,4,-1,2,1,-5,4], where the subarray [4,-1,2,1] yields the maximum sum of 6. Two implementations of the solution in Java are presented, demonstrating different approaches to calculate the maximum subarray sum.

Uploaded by

Vidyashankar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Maximum Subarray

Find the contiguous subarray within an array(containing at least on number) which has the largest sum.

Given the array [-2,1,-3,4,-1,2,1,-5,4] the contiguous subaray[4,-1,2,1] has the largest sum = 6

public class Solution{


public int maxSubarray(int[] A){
int max = A[0];
int[] sum = new int[A.length];
sum[0] = A[0];

for(int i = 1; i < A.length;i++){


sum[i] = Math.max(A[i],sum[i-1] + A[i]);
max = Math.max(max,sum[i]);
}
return max;
}
}
-----------------------------

public int maxSubarray(int[] A){


int newsum = A[0];
int max = A[0];
for(int i=1;i<A.length;i++){
newsum = Math.max(newsum+A[i],A[i]);
max = Math.max(max,newsum);
}
return max;
}

You might also like