-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathMaxSubArray.java
More file actions
107 lines (98 loc) · 2.57 KB
/
Copy pathMaxSubArray.java
File metadata and controls
107 lines (98 loc) · 2.57 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import java.util.*;
class MaxSubArray
{
public static SubArray maxSubArray(int[] arr,int low,int high)
{
if (high==low)
{
return new SubArray(low,high,arr[low]);
}
else
{
int mid=(int) (low+high)/2;
SubArray leftSubArray=maxSubArray(arr,low,mid);
SubArray rightSubArray=maxSubArray(arr,mid+1,high);
SubArray crossSubArray=maxCrossSubArray(arr,low,mid,high);
if(leftSubArray.getSum()>=rightSubArray.getSum() && leftSubArray.getSum()>=crossSubArray.getSum())
return leftSubArray;
if(rightSubArray.getSum()>=leftSubArray.getSum() && rightSubArray.getSum()>=crossSubArray.getSum())
return rightSubArray;
else
return crossSubArray;
}
}
public static SubArray maxCrossSubArray(int[] arr,int low,int mid,int high)
{
int leftSum=Integer.MIN_VALUE;
int sum=0;
int maxLeft=low;
int maxRight=high;
for(int i=mid;i>=low;i--)
{
sum=sum+arr[i];
if(sum>leftSum)
{
leftSum=sum;
maxLeft=i;
}
}
int rightSum=Integer.MIN_VALUE;
sum=0;
for(int j=mid+1;j<=high;j++)
{
sum=sum+arr[j];
if(sum>rightSum)
{
rightSum=sum;
maxRight=j;
}
}
return new SubArray(maxLeft,maxRight,(leftSum+rightSum));
}
static class SubArray
{
int start;
int end;
int sum;
SubArray(){}
public SubArray(int start,int end,int sum)
{
super();
this.start=start;
this.end=end;
this.sum=sum;
}
public int getStart(){ return start; }
public void setStart(int start){ this.start=start; }
public int getEnd(){ return end; }
public void setEnd(int end){ this.end=end; }
public int getSum(){ return sum; }
public void setSum(int sum){ this.sum=sum; }
public String toString()
{
return "SubArray [Start=" +start+ ",end=" +end+ ",Sum=" +sum+ "]" ;
}
/* void print()
{
int ar[]=new int[(start-end)+1];
for(int i=start;i<=end;i++)
System.out.print(ar[i]+" ");
}
*/
}
public static void main(String ar[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter Size of Array");
int n=sc.nextInt();
int arr[]=new int[n];
System.out.println("Enter the array elements");
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
System.out.println("Maximum SubArray for array "+ Arrays.toString(arr)+": "+ maxSubArray(arr,0,n-1));
//SubArray ob=new SubArray();
//ob.print();
}
}