【アルゴリズムデータ構造Java実装】時間複雑度O(n)の最大和シーケンス
1034 ワード
1.背景
最大シーケンスと問題はずっと古典的なアルゴリズム問題であり,この問題を見ると,多くの解題方法がある.今日,時間的複雑度がO(n)のみの解題アルゴリズムが見られ,ここで記録される.
考え方は簡単です.例えば、P 1、P 2、P 3、P 4があります.このようなシーケンスでは,P 1から和を求める,例えばP 5で和を求める数がゼロ未満であると断定できる.第1の場合、最大シーケンスはP 1~P 5の間、あるいはP 6~Pnの間である.P 1+P 2+......+P 5の和がゼロ未満であれば、1つの数と見なすことができ、シーケンスの最初の数であれば、どの最大シーケンスもこの数を含まない.
2.コード実装
参照先:http://blog.csdn.net/superchanon/article/details/8228212(完全な4つの実装方法)
/********************************
*ブログ「李博Garvin」より
*転載は出典を明記してください:http://blog.csdn.net/buptgshengod
******************************************/
最大シーケンスと問題はずっと古典的なアルゴリズム問題であり,この問題を見ると,多くの解題方法がある.今日,時間的複雑度がO(n)のみの解題アルゴリズムが見られ,ここで記録される.
考え方は簡単です.例えば、P 1、P 2、P 3、P 4があります.このようなシーケンスでは,P 1から和を求める,例えばP 5で和を求める数がゼロ未満であると断定できる.第1の場合、最大シーケンスはP 1~P 5の間、あるいはP 6~Pnの間である.P 1+P 2+......+P 5の和がゼロ未満であれば、1つの数と見なすことができ、シーケンスの最初の数であれば、どの最大シーケンスもこの数を含まない.
2.コード実装
package Algorithm_analysis;
public class MaxSumOfArray {
public static void main(String args[]){
System.out.print(max_sum());
}
public static int max_sum(){
int[] array={-2,11,-4,13,-5,-2};
int max_sum=0;
int array_sum=0;
for(int j=0;jmax_sum)
{
max_sum=array_sum;
}
}
return max_sum;
}
}
参照先:http://blog.csdn.net/superchanon/article/details/8228212(完全な4つの実装方法)
/********************************
*ブログ「李博Garvin」より
*転載は出典を明記してください:http://blog.csdn.net/buptgshengod
******************************************/