最大子数组和

package Test;

 import java.util.Scanner;
public class MaxSubArray {
     public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);
         System.out.println("输入数组长度");
         int n = scan.nextInt();
         int[] a = new int[n];

         System.out.println("输入数组元素");
         for(int i = 0;i < n;i++)
         {
             a[i] = scan.nextInt();20         }
         scan.close();

         int[] result = maxSub(a,a.length);
         System.out.println("不连接成环的和最大的连续子数组：");
         for(int i = result[0];i <= result[1];i++)
         {
             System.out.print(a[i] + "	");
         }
         System.out.println("和为：" + result[2]);

        int[] b = new int[2 * n - 1];
         for(int i = 0;i < n - 1;i++)
         {
             b[i] = a[i];
             b[n + i] = a[i];
         }
         b[n - 1] = a[n - 1];
         int[] result2 = maxSub(b,n);
         System.out.println("

将数组连成环后的和最大的连续子数组：")
         for(int i = result2[0];i <= result2[1];i++)
         {
             System.out.print(b[i] + "	");
        }
         System.out.println("和为：" + result2[2]);


     }

     public static int[] maxSub(int[] a,int n)
     {         int an = a.length;
         int currectSum = a[0];
         int currectStartIndex = 0;
         int count = 1;
         int[] result = new int[3];
         result[0] = 0;
         result[1] = 0;
         result[2] = a[0];
        for(int i = 1;i < an;i++)
         {
             if(currectSum <= 0)
             {
                currectSum = a[i];
               currectStartIndex = i;
                count = 1;
            }
            else
             {
                currectSum += a[i];
                 count++;
            }
            if(currectSum > result[2])
            {
                result[0] = currectStartIndex;
                result[1] = i;
                 result[2] = currectSum;
            }
             if(count >= n)
             {
                 break;
             }
        }
        return result;
     }
}

思路：

把每一种起点情况下的最大子数组之和S求出，存入S[]数组中，最后比较S[]中的最大值（i为数组的长度）存为MaxSum。而此时的起点-finalStart和终点-finalEnd也同样可以在求MaxSum的同时记录下来。