Maximum Subarray Problem

Problem Definition- Find out a sub-array from n array of numbers where the sum is highest.

SolutionĀ  type: Brute force, find out all the combination of arrays and pick the one with maximum sum

Order of complexity: N^2

Code:
public class maxsubarray {

public static void main(String s[])
{
int arr[]={-1,2,4,60,1,-3,2,-6,7,-9,1};

int maxsum=0;
int maxlow=0;
int maxhigh=0;
int low=0;
int high=0;
int sum=0;
int newsum=0;
for(int i=0;i<arr.length-1;i++)
{
sum=0;
newsum=0;
sum=arr[i]+arr[i+1];
newsum=sum;
low=i;
high=i+1;
for(int j=i+2;j<arr.length;j++)
{
newsum=newsum+arr[j];
if(sum<newsum)
{
sum=newsum;
high=j;

}
}
if(sum>maxsum)
{
maxsum=sum;
maxhigh=high;
maxlow=low;
}
}
System.out.println(“lower bound:”+maxlow);
System.out.println(“higher bound:”+maxhigh);
System.out.println(“maximum sum:”+maxsum);
}
}