This problem is called Maximum contiguous sub sequence sum problem.
Given an array which can contain both positive and negative numbers, find the maximum contiguous sub sequence sum.
For example in an array = {2, -3, 4, -5, 6, -3, 8}, it should return 11.
Algo :
Take the array, {2, -3, 4, -5, 6, -3, 8}
Compute the partial sums up to place i for all i, {2, -1, 3, -2, 4, 1, 9}
Subtract from each element the minimum that occurs earlier (or 0), {2, -1, 4, -1, 6, 3, 11}
Take the maximum, 11
Code:
public class maxSubSeq
{
public static void main(String args[])
{
....int[] a = {2,-3,4,-5,6,-3,8};
....int[] p = new int[a.length];
....//Compute partial sums
....for(int i = 0; i ....{
....if(i==0)
.......p[i] = a[i] ;
....else
.......p[i] = a[i] + p[i-1];
....}
....//Substract from each element in p, the minimum that occur
....//earlier (or 0)
....int min=0;
....for(int i=0; i< p.length; i++)
....{
....if(i==0)
....{
....if(p[i] > 0)
........min = 0;
....else
........min = p[i];
..... p[i] = p[i] - min;
...}
....else
... {
....if(p[i] < min)
.......min = p[i];
....... p[i] = p[i] - min;
}
}
//Maximum of the resulting p would be the maximum subsequence
java.util.Arrays.sort(p);
System.out.println("The maximum subsequence - " + p[p.length-1]);
}
}
Given an array which can contain both positive and negative numbers, find the maximum contiguous sub sequence sum.
For example in an array = {2, -3, 4, -5, 6, -3, 8}, it should return 11.
Algo :
Take the array, {2, -3, 4, -5, 6, -3, 8}
Compute the partial sums up to place i for all i, {2, -1, 3, -2, 4, 1, 9}
Subtract from each element the minimum that occurs earlier (or 0), {2, -1, 4, -1, 6, 3, 11}
Take the maximum, 11
Code:
public class maxSubSeq
{
public static void main(String args[])
{
....int[] a = {2,-3,4,-5,6,-3,8};
....int[] p = new int[a.length];
....//Compute partial sums
....for(int i = 0; i
....if(i==0)
.......p[i] = a[i] ;
....else
.......p[i] = a[i] + p[i-1];
....}
....//Substract from each element in p, the minimum that occur
....//earlier (or 0)
....int min=0;
....for(int i=0; i< p.length; i++)
....{
....if(i==0)
....{
....if(p[i] > 0)
........min = 0;
....else
........min = p[i];
..... p[i] = p[i] - min;
...}
....else
... {
....if(p[i] < min)
.......min = p[i];
....... p[i] = p[i] - min;
}
}
//Maximum of the resulting p would be the maximum subsequence
java.util.Arrays.sort(p);
System.out.println("The maximum subsequence - " + p[p.length-1]);
}
}
0 comments:
Post a Comment