求数组最大平均值的连续子序列、最大和的连续子序列

算法是我最头疼的问题，经常被问到就懵逼，但是后来一想就能想起来，也是没那么能难，人啊就是要多总结，人类的进步就是因为人把知识记载了下来，后来的人有了前人的经验教训，总会成长，慢慢成长。在岁月的长河中，知识达到了沉淀，孕育了很多伟大的民族文化。。。

实在编不下去了，赶紧进入正题，同学啊，在你看到题目的时候也是一脸懵逼，如果是的话，那就对了，证明你没看过类似的算法，看到题目有种似懂非懂的感觉，光是理解题目就是很费劲，没错，因为这个题就是考的脑筋急转弯？啥，不明白啊，等我说完你就知道了。。。

还在扯什么啊，怎么还不进入正题呢？很多人肯定要骂我了，其实 我是留给大家思考的时间，因为大家再看这段废话的时候大脑却在想着我的问题，为什么我·会这么说，哈哈 我看过最强大脑，去年这个的时候，我因为最强大脑，花了一个月的时间专门去训练了记忆力，你还别说，还真有效果。我先练习的定桩，110数字桩，懂的同学知道我在说什么，不懂的同学我也不会在这说了，给你个传送门，好吧开始进入正题吧。

package zong.xiao.mi.demosource.java;

/**
 * Created by mi on 2017/4/5.
 */

public class 最大平均值的连续子序列 {


  public static int[] array = {-2, 3, -5, 4, 1, -1, 2};

  public static void main(String[] arguments) {
    maxAverage(array);
    maxSum(array);
  }



  /**
   * 求数组的最大平均值的连续子序列（连续子序列：元素个数大于等于2）
   * 
   * @return
   */
  public static int[] maxAverage(int[] array) {

    int length = array.length;
    int sum;
    float currentAvg = 0;// 当前的平均值
    int markI = 0;// 标记连续子序列的起始下标
    int markJ = 0;// 标记连续子序列的结束下标
    for (int i = 0; i < length; i++) {
      sum = 0;// 重置sum
      for (int j = i; j < length; j++) {
        sum = sum + array[j];// 累积求和
        float avg = (float) sum / (j - i + 1);
        if (avg > currentAvg && i != j) {// 如果起始下标等于结束下标，就是表明是单个元素，此块要排除
          markJ = j;
          markI = i;
          currentAvg = avg;
        }
      }
    }
    int arr[] = new int[markJ - markI + 1];
    System.arraycopy(array, markI, arr, 0, markJ - markI + 1);

    System.out.println("最大平均值==" + currentAvg + "-在数组中的起始位置==" + markI + "-数组中的结束位置==" + markJ);
    return arr;
  }

  /**
   * 最大和的连续子序列
   * 时间复杂度O（N^2）
   * @param array
   * @return
   */
  public static int[] maxSum(int array[]) {
    if (array == null || array.length == 0) return null;
    int length = array.length;
    int sum = 0;
    int currentSum = 0;
    int markStart = 0;
    int markEnd = 0;

    for (int i = 0; i < length; i++) {
      sum = 0;
      for (int j = i; j < length; j++) {
        sum += array[j];
        if (sum > currentSum) {
          markStart = i;
          markEnd = j;
          currentSum = sum;
        }
      }
    }
    int[] copy = new int[markEnd - markStart + 1];
    System.arraycopy(array, markStart, copy, 0, markEnd - markStart + 1);
    System.out
        .println("最大和==" + currentSum + "-在数组中的起始位置==" + markStart + "-数组中的结束位置==" + markEnd);
    return copy;
  }
}

多么简单粗暴，代码自己看吧，注释都在上面。
补充求和的第二种方法，性能更优。

二

/**
   * 最大和的连续子序列第二种方法
   *
   * 时间复杂度O(N)
   * 
   * @param array
   * @return
   */
  public static int[] maxSum2(int array[]) {

    int temp = 0;
    int currentMax = 0;
    int length = array.length;
    int start = 0;// 标记开始位置
    int end = 0;// 标记结束位置

    for (int i = 0; i < length; i++) {
      if (temp + array[i] > 0) {
        temp = temp + array[i];
      } else {
        temp = 0;
        start = i + 1;
      }

      if (temp > currentMax) {
        end = i;
        currentMax = temp;
      }
    }
    System.out.println(currentMax + "start==" + start + "end==" + end);
    return null;
  }

第二个算法的时间复杂度最好，只用了一遍遍历

说个注意的点，什么是连续子序列，我认为啊这个连续子序列的元素的个数要大于两个才能算连续子序列。如果没有这个限制会怎么样？
如果没有这个限制，上边数组中的最大连续子序列 我不用算就知道是4 ，我不相信哪个子序列的平均值会大于4，为什么，因为任何一个数，加上比自己小的数，再求平均值，肯定没有这个数大。如果有这个限制，那就从所有含有两个元素的子序列里面找。因为三个数的平均值肯定没有两个的数的平均值大。如果这几个元素都是一样大小值的 你就别给我扯淡了。。

最大平均值的连续子序列： 求出数组所有的连续子序列，对每个连续子序列求平均值，找最大的一个。