How to get Maximum Subarray Sum in optimal way

How to get Maximum Subarray Sum in optimal way

Maximum sub array  

Given an array with both positive and negative integers and need to find the sum of contiguous subarray of numbers which has the largest sum along with the index values like start and end index from the given array. Also time complexity with O(N)

For example, if the given array is {-2, 5, 4, -3, 6, 9, -1}, then the maximum subarray sum is 21 and array index from 1 to 5 which is  5 + 4 + -3 + 6 + 9 = 21.

Solution:

• Define each 2 variables for sum, start index and for end index. 
• 1st sum and index points will hold each block of sum until its values <= 0. 
• If any negative value comes in iteration then compare the 1st sum with 2nd (which holds the maximum subarray sum) sum and copy if its greater. 
• Iterate until array end and get the maximum subarray sum with the complexity of O(N)

If there are any better solution please post it under below comments section and sharing makes better.

public class SubArray {

 public static void main(String[] args) {

  int array[] = new int[] { -2, 5, 4, -3, 6, 9, -1 };

  SubArray obj = new SubArray();

  obj.getMaximumSumSubArray(array);
 }

 public void getMaximumSumSubArray(int[] array) {

  int start = 0, end = 0, sum = 0, finalSum = 0, fStart = 0, fEnd = 0;

  for (int i = 0; i < array.length; i++) {

   // Avoid initial array with negative
   if (array[i] > 0 && sum == 0) {
    start = end = i;
    sum = array[i];

    // Add current value with sum
   } else if (array[i] > 0) {
    end = i;
    sum += array[i];

   } else {
    // Copy sum to finalSum if sum > finalSum
    if (sum > finalSum) {
     finalSum = sum;
     fStart = start;
     fEnd = end;
    }

    // If sum + current <= 0 then start new sum
    if ((array[i] + sum) <= 0) {
     sum = 0;

    } else {
     sum += array[i];
    }
   }
  }

  // Last compare, sum and finalSum
  if (sum > finalSum) {
   finalSum = sum;
   fStart = start;
   fEnd = end;
  }

  System.out.println("Sum         : " + finalSum);
  System.out.println("Start Index : " + fStart);
  System.out.println("End Index   : " + fEnd);

 }
}

OUPUT:

Sum         : 21
Start Index : 1
End Index   : 5