【面接でよくあるテーマのダイナミックプランニング】連続サブシーケンスの最大和(サブ配列の最大和)
タイトル:
整形配列を入力します.配列には正数も負数もあります.配列内の連続する1つ以上の整数は、1つのサブ配列を構成し、各サブ配列には1つの和があります.すべてのサブ配列の和の最大値を求めます.要求時間複雑度はO(n)である.
考え方:
まず、これは古いテーマですが、書き間違えやすいので、ある外資系企業の面接で、面接官のいくつかのtest caseに論理的な間違いを測定されました.
アルゴリズムは次のとおりです.現在の最大和を仮定します.
MAX、連続加算がゼロでない和
SUM、配列の現在のスキャン値
A[i];
則
if (SUM > MAX) MAX = SUM;
if (A[i] > MAX) MAX = A[i];
if (SUM < 0) SUM = 0;
最後に,全負数の場合,最初からもう一度スキャンし,最大の負数を選択する必要がある.
コードとテスト例
整形配列を入力します.配列には正数も負数もあります.配列内の連続する1つ以上の整数は、1つのサブ配列を構成し、各サブ配列には1つの和があります.すべてのサブ配列の和の最大値を求めます.要求時間複雑度はO(n)である.
考え方:
まず、これは古いテーマですが、書き間違えやすいので、ある外資系企業の面接で、面接官のいくつかのtest caseに論理的な間違いを測定されました.
アルゴリズムは次のとおりです.現在の最大和を仮定します.
MAX、連続加算がゼロでない和
SUM、配列の現在のスキャン値
A[i];
則
if (SUM > MAX) MAX = SUM;
if (A[i] > MAX) MAX = A[i];
if (SUM < 0) SUM = 0;
最後に,全負数の場合,最初からもう一度スキャンし,最大の負数を選択する必要がある.
コードとテスト例
#include <iostream>
using namespace std;
int max_seq_sum(int a[], int len) {
int max = a[0];
int sum = 0;
for (int i = 0; i < len; i++) {
sum += a[i];
if (sum > max) {
max = sum;
}
if (a[i] > max) {
max = a[i];
}
if (sum < 0) {
sum = 0;
}
}
if (0 == max) {
max = a[0];
for (int i = 0; i < len; i++) {
if (a[i] > max) {
max = a[i];
}
}
}
return max;
}
int main() {
int a[] = {10, -2, -3};
int b[] = {-10, -2, -3};
int c[] = {3, -2, 10};
cout << max_seq_sum(a, 3) << endl;
cout << max_seq_sum(b, 3) << endl;
cout << max_seq_sum(c, 3) << endl;
}