4.1-5使用線性時間開銷的算法得出最大子數(shù)組

先做如下規(guī)定：

數(shù)組下標(biāo)從1開始

當(dāng)說A[i,j]的值時，指該子數(shù)組中所有元素的和

題目:

思路:

題目中給出的思路屬于動態(tài)規(guī)劃，使用已經(jīng)計算出的結(jié)果輔助接下來的計算

如題目所述，若已知A[1,j]中的最大子數(shù)組，A[1,j+1]中的最大子數(shù)組要么為A[1,j]中的最大子數(shù)組，要么為A[i,j+1]的最大值

如果A[1,j+1]中最大子數(shù)組為A[i,j+1]的最大值,確定i值時對所有的i可能取值(1<=i<=j+1)進行比較，這將花費O(n),使算法時間復(fù)雜度為O(n^2),但在動態(tài)規(guī)劃中，在已知A[1,j]中的形如A[i,j]的子數(shù)組的最大值的i取值時，可以在O(1)時間得出A[i,j+1]取最大值時i的取值，使算法時間復(fù)雜度為O(n)

以下是對在已知A[1,j]中,A[i,j]最大時i取值時求A[1,j+1]中A[i,j+1]的分析

已知A[1,j]中,A[i,j]的最大值在i=k時取得

對于A[1,j+1]中A[i,j+1]，在從j+1 向1 遍歷i的值時可想象這樣一個過程，不斷有元素被添加到A[i,j+1]這個數(shù)組里來，要對每個A[i,j+1]的值進行比較

A[i,j+1]的結(jié)果將有兩種,加入A[j],不加入A[j],

如果不加入A[j]那么i的取值為j+1；

如果加入A[j],那么其必須加入整個A[k,j],因為A[k,j]是A[1,j]中A[i,j]的最大子數(shù)組，加入其他數(shù)組的結(jié)果都小于加入A[k,j];

?

綜上，我們尋找的A[1,j+1]中的最大子數(shù)組，既A[1,j]中最大子數(shù)組,A[j+1],A[k,j]+A[j+1],三個數(shù)組中的最大數(shù)組

數(shù)學(xué)表達(dá):

先定義:

msA[1,j]=find_max_subarray(A[1,j])

迭代式:

A[1,j+1]=max(msA[1,j],A[j+1],A[k,j]+A[j+1])

c++實現(xiàn):

#include<iostream>

struct FindMaxSubarrayReturn {

??? int begin;

??? int len;

??? int sum;

};

class FindMaxSubarray

{

public:

??? FindMaxSubarrayReturn find_max_subarray_non_recursion(int* v, int begin, int len);

??? void test_non_recursion();

?

};

FindMaxSubarrayReturn FindMaxSubarray::find_max_subarray_non_recursion(int* v, int begin, int len)

{

??? int k = 0;

??? int right = 0;

??? int left = 0;

??? int sum1=v[begin];//for msA[1,j]

??? int sum2 = v[begin];//for msA[k,j]

??? for (int i = 1; i < begin + len; i++) {

???????? if (sum1 >= v[i] &&sum1>=v[i]+sum2) {

?

???????? }

???????? else if (v[i] >= sum1 && v[i] >= sum2 + v[i]) {

???????????? left = i;

???????????? right = i;

???????????? sum1 = v[i];

???????? }

???????? else {

???????????? left = k;

???????????? right = i;

???????????? sum1 = sum2 + v[i];

???????? }

???????? if (v[i] >= sum2 + v[i]) {

???????????? k = i;

???????????? sum2 = v[i];

???????? }

???????? else {

???????????? sum2 += v[i];

???????? }

??? }

??? FindMaxSubarrayReturn ret;

??? ret.begin = left;

??? ret.len = right - left +1;

??? ret.sum = sum1;

??? return ret;

}

void FindMaxSubarray::test_non_recursion()

{

??? int v[] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };

??? FindMaxSubarrayReturn ret;

??? ret = find_max_subarray_non_recursion(v, 0, 16);

??? std::cout << "result: " << std::endl;

??? std::cout << "length: " << ret.len << std::endl;

??? for (int i = 0; i < ret.len; i++) {

???????? std::cout << v[i + ret.begin];

???????? std::cout << " ";

??? }

??? std::cout << std::endl;

??? std::cout <<"sum: "<< ret.sum << std::endl;

}

int main(int argc,char* argv[]) {

??? FindMaxSubarray find_max_subarray;

??? find_max_subarray.test_non_recursion();

??? return 0;

}