Lettcode.53_Maximum Subarray
この文章は学習中のまとめです。転載を歓迎しますが、出典を明記してください。http://blog.csdn.net/pistolove/article/details/43989997
Find the contigous subarray within an array(containing at least one number)which has the larget sum.
For example、given the array
考え方:
（1）与えられた整数配列を意味し、配列中の連続的なサブ配列の和の最大値を求める。
（2）これは比較的古典的な筆記試験の面接問題です。行列の運用についての主要な考察。配列中の要素は正であり、負でもありますので、連続要素の最大値を得るには、配列遍歴中に負の値が発生した場合に判断する必要があります。このように、配列を1回通過するだけで（現在の連続シーケンスの和sum=0を初期化し、最大値max=x[0]）、遍歴している間に、現在のsum>=0の場合、連続シーケンスの和が正であることを示し、現在のエルゴード要素の値をsumに加算する。sum<0の場合、前遍歴中に負の値が発生したと説明し、現在のエルゴード要素の数値をsumに賦与する。sumが現在の最大値maxより大きい場合、sumの値はmaxに割り当てられる。配列を巡回した後、maxは求められます。
（3）この問題は主に正と負の数が入れ替わる場合と全部マイナスの場合を考慮して、詳細は下のコードを参照してください。この文章があなたの役に立ちますように。
アルゴリズムコードは以下の通り実現される。
Find the contigous subarray within an array(containing at least one number)which has the larget sum.
For example、given the array
[−2,1,−3,4,−1,2,1,−5,4]、the contigous subarray [4,−1,2,1] has the larget sum= 6.考え方:
（1）与えられた整数配列を意味し、配列中の連続的なサブ配列の和の最大値を求める。
（2）これは比較的古典的な筆記試験の面接問題です。行列の運用についての主要な考察。配列中の要素は正であり、負でもありますので、連続要素の最大値を得るには、配列遍歴中に負の値が発生した場合に判断する必要があります。このように、配列を1回通過するだけで（現在の連続シーケンスの和sum=0を初期化し、最大値max=x[0]）、遍歴している間に、現在のsum>=0の場合、連続シーケンスの和が正であることを示し、現在のエルゴード要素の値をsumに加算する。sum<0の場合、前遍歴中に負の値が発生したと説明し、現在のエルゴード要素の数値をsumに賦与する。sumが現在の最大値maxより大きい場合、sumの値はmaxに割り当てられる。配列を巡回した後、maxは求められます。
（3）この問題は主に正と負の数が入れ替わる場合と全部マイナスの場合を考慮して、詳細は下のコードを参照してください。この文章があなたの役に立ちますように。
アルゴリズムコードは以下の通り実現される。
/**
* @author liqq
*/
public class Maximum_Subarray{
public int maxSubArray(int[] x) {
if(x==null || x.length==0) return 0;
int sum = 0;
int max = x[0];
for (int i = 0; i < x.length; i++) {
if(sum>=0){
sum = sum+x[i];
}else{
sum=x[i];
}
if(sum>max){
max = sum; }
}
// for (int i = 0; i < x.length; i++) {
// for (int j = i; j < x.length; j++) {
// for (int k = i; k <= j; k++) {
// sum = sum + x[k];
// }
// if(MaxSum<sum){
// MaxSum = sum;
// }
// sum=0;
// }
// }
return max;
}
}