算法是我最頭疼的問題，經(jīng)常被問到就懵逼嚎杨，但是后來一想就能想起來花鹅，也是沒那么能難，人啊就是要多總結(jié)枫浙，人類的進(jìn)步就是因?yàn)槿税阎R(shí)記載了下來刨肃，后來的人有了前人的經(jīng)驗(yàn)教訓(xùn)，總會(huì)成長(zhǎng)箩帚，慢慢成長(zhǎng)真友。在歲月的長(zhǎng)河中，知識(shí)達(dá)到了沉淀紧帕，孕育了很多偉大的民族文化盔然。桅打。。
實(shí)在編不下去了愈案，趕緊進(jìn)入正題挺尾，同學(xué)啊，在你看到題目的時(shí)候也是一臉懵逼站绪，如果是的話遭铺，那就對(duì)了，證明你沒看過類似的算法恢准，看到題目有種似懂非懂的感覺魂挂，光是理解題目就是很費(fèi)勁，沒錯(cuò)馁筐，因?yàn)檫@個(gè)題就是考的腦筋急轉(zhuǎn)彎涂召？啥，不明白啊眯漩，等我說完你就知道了芹扭。。赦抖。
還在扯什么啊舱卡，怎么還不進(jìn)入正題呢？很多人肯定要罵我了队萤，其實(shí) 我是留給大家思考的時(shí)間轮锥，因?yàn)榇蠹以倏催@段廢話的時(shí)候大腦卻在想著我的問題，為什么我·會(huì)這么說要尔，哈哈 我看過最強(qiáng)大腦舍杜，去年這個(gè)的時(shí)候，我因?yàn)樽顝?qiáng)大腦赵辕，花了一個(gè)月的時(shí)間專門去訓(xùn)練了記憶力既绩，你還別說，還真有效果还惠。我先練習(xí)的定樁饲握，110數(shù)字樁，懂的同學(xué)知道我在說什么蚕键，不懂的同學(xué)我也不會(huì)在這說了救欧，給你個(gè)傳送門，好吧開始進(jìn)入正題吧锣光。
package zong.xiao.mi.demosource.java;
/**
* Created by mi on 2017/4/5.
*/
public class 最大平均值的連續(xù)子序列 {
public static int[] array = {-2, 3, -5, 4, 1, -1, 2};
public static void main(String[] arguments) {
maxAverage(array);
maxSum(array);
}
/**
* 求數(shù)組的最大平均值的連續(xù)子序列（連續(xù)子序列：元素個(gè)數(shù)大于等于2）
*
* @return
*/
public static int[] maxAverage(int[] array) {
int length = array.length;
int sum;
float currentAvg = 0;// 當(dāng)前的平均值
int markI = 0;// 標(biāo)記連續(xù)子序列的起始下標(biāo)
int markJ = 0;// 標(biāo)記連續(xù)子序列的結(jié)束下標(biāo)
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) {// 如果起始下標(biāo)等于結(jié)束下標(biāo)笆怠，就是表明是單個(gè)元素，此塊要排除
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 + "-在數(shù)組中的起始位置==" + markI + "-數(shù)組中的結(jié)束位置==" + markJ);
return arr;
}
/**
* 最大和的連續(xù)子序列
* 時(shí)間復(fù)雜度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 + "-在數(shù)組中的起始位置==" + markStart + "-數(shù)組中的結(jié)束位置==" + markEnd);
return copy;
}
}
多么簡(jiǎn)單粗暴誊爹，代碼自己看吧蹬刷，注釋都在上面瓢捉。
補(bǔ)充求和的第二種方法，性能更優(yōu)办成。
二
/**
* 最大和的連續(xù)子序列第二種方法
*
* 時(shí)間復(fù)雜度O(N)
*
* @param array
* @return
*/
public static int[] maxSum2(int array[]) {
int temp = 0;
int currentMax = 0;
int length = array.length;
int start = 0;// 標(biāo)記開始位置
int end = 0;// 標(biāo)記結(jié)束位置
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;
}
第二個(gè)算法的時(shí)間復(fù)雜度最好泊柬，只用了一遍遍歷
說個(gè)注意的點(diǎn)，什么是連續(xù)子序列诈火，我認(rèn)為啊這個(gè)連續(xù)子序列的元素的個(gè)數(shù)要大于兩個(gè)才能算連續(xù)子序列。如果沒有這個(gè)限制會(huì)怎么樣状答？
如果沒有這個(gè)限制冷守，上邊數(shù)組中的最大連續(xù)子序列 我不用算就知道是4 ，我不相信哪個(gè)子序列的平均值會(huì)大于4惊科，為什么拍摇，因?yàn)槿魏我粋€(gè)數(shù)，加上比自己小的數(shù)馆截，再求平均值充活，肯定沒有這個(gè)數(shù)大。如果有這個(gè)限制蜡娶，那就從所有含有兩個(gè)元素的子序列里面找混卵。因?yàn)槿齻€(gè)數(shù)的平均值肯定沒有兩個(gè)的數(shù)的平均值大。如果這幾個(gè)元素都是一樣大小值的 你就別給我扯淡了窖张。幕随。
最大平均值的連續(xù)子序列： 求出數(shù)組所有的連續(xù)子序列，對(duì)每個(gè)連續(xù)子序列求平均值宿接，找最大的一個(gè)赘淮。
