Thursday, April 3, 2014

Maximum segment sum in Java

public class MaxSegSum
{
  private int beg_tmp, end, beg = 0;
 
  /* maxe = maximum ending here <=> cumulative sum
   * maxs = maximum so far
   */
  public int doSegSum(int a[], int sz)
  {
    int maxe = a[0], maxs = a[0];
    for (int i = 1 ; i < sz ; i++)
    {
       if (maxe < 0)
       {
         beg_tmp = i;
         maxe = a[i];
       }
       else
         maxe += a[i];
      
       if (maxe >= maxs)
       {
          maxs = maxe;
          beg = beg_tmp;
          end = i; 
       }
    }
    return maxs;
  }
 
  public static void main(String args[])
  {
    int A[] = {1, -2, 2, -1, 3, 4};
    System.out.println("value is " + new MaxSegSum().doSegSum(A, 6));
  } 
}

No comments:

Post a Comment