sub array using prefix sum
public class MaxSubArray_Prefixsum{
public static void maxPrefixSubarray(int numbers[]){
int ts=0;
int maxSum=Integer.MIN_VALUE;
int prefix[]=new int[numbers.length];
prefix[0]=numbers[0];
//creating prefix array
for(int i=1;i<numbers.length;i++){
prefix[i]=numbers[i]+prefix[i-1];
}
System.out.println("prefix array is");
for(int i=0;i<numbers.length;i++){
System.out.print(prefix[i]+" ");
}
System.out.println("sapce");
for(int i=0;i<numbers.length;i++){
int sum=0;
for(int j=i; j<numbers.length;j++){
sum = i==0 ? prefix[j]:prefix[j]-prefix[i-1];
System.out.print(sum+" ");
}
if(maxSum<sum){
maxSum=sum;
}
}
System.out.println("Maximum sum is "+maxSum);
}
public static void main(String[] args) {
int numbers[]={2, 4, 6, 8, 10};
maxPrefixSubarray(numbers);
}
}
Comments
Post a Comment