public class MSSum {
    public static void main(String[] args) {
        MSSum mSSum = new MSSum();
        mSSum.findSum(new int[]{
          1,-1,2,3,-1,5,-2,99
        }
        );
    }
    public void findSum(int[] a){
      int as=0;int ae=0;int asum=-999999;
      int cs=0;int ce=0;int csum=0;
      int i;
      for (i = 0; i < a.length; i++)  {
       csum+=a[i];
       if(csum>asum){
        asum=csum;ae=i;as=cs;
       }
       if(csum<=0){
        while(i<a.length && a[i+1]<=0)i++;
        cs=i+1;ce=i;csum=0;
       }
      }
      if(cs>asum){
         asum=csum;ae=i;as=cs;
      }
      System.out.println("Maximum Subset Sum starts from "
        +as+" and ends at "+ae+" with sum="+asum);   
    }
}