# 最大子序列和问题之算法优化

int maxSubsequenceSum(const int a[], int n) { int i, j, k; int thisSum, maxSum = 0; for (i = 0; i < n; i++) for (j = i; j < n; j++) { thisSum = 0; for (k = i; k < j; k++) thisSum += a[k]; if (thisSum > maxSum) maxSum = thisSum; } return maxSum; }

int maxSubsequenceSum(const int a[], int n) { int i, j; int thisSum, maxSum = 0; for (i = 0; i < n; i++) { thisSum = 0; for (j = i; j < n; j++) { thisSum += a[j]; if (thisSum > maxSum) maxSum = thisSum; } } return maxSum; }

### 算法三：分治（divide-and-conquer）策略

#### 分治策略：

int maxSubsequenceSum(const int a[], int left, int right) { int i, mid, maxLeftSum, maxRightSum; int maxLeftBorderSum, leftBorderSum; int maxRightBorderSum, rightBorderSum; if (left == right) { /*基准情况*/ if (a[left] >= 0) return a[left]; else return 0; } mid = left + (right - left) / 2; maxLeftSum = maxSubsequenceSum(a, left, mid); /*左半部分的最大和*/ maxRightSum = maxSubsequenceSum(a, mid+1, right); /*右半部分的最大和*/ /*下面求穿过中点的最大和*/ maxLeftBorderSum = 0, leftBorderSum = 0; for (i = mid; i >= left; i--) /*中点及其以左的最大和*/ { leftBorderSum += a[i]; if (leftBorderSum > maxLeftBorderSum) maxLeftBorderSum = leftBorderSum; } maxRightBorderSum = 0, rightBorderSum = 0; for (i = mid+1; i <= right; i++) /*中点以右的最大和*/ { rightBorderSum += a[i]; if (rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum; } /*返回三部分中的最大值*/ return max3(maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum); } int max3(int a, int b, int c) { int maxNum = a; if (b > maxNum) maxNum = b; if (c > maxNum) maxNum = c; return maxNum; }

T(1) = 1 T(n) = 2T(n/2) + O(n)

### 算法四：

int maxSubsequenceSum(const int a[], int n) { int i; int maxSum, thisSum; maxSum = thisSum = 0; for (i = 0; i < n; i++) { thisSum += a[i]; if (thisSum > maxSum) maxSum = thisSum; else if (thisSum < 0) thisSum = 0; } return maxSum; }

463 篇文章153 人订阅

0 条评论

## 相关文章

### 压缩感知重构算法之正则化正交匹配追踪(ROMP)

在看代码之前，先拜读了ROMP的经典文章：Needell D，VershyninR．Signal recovery from incompleteand i...

37360

### n-gram

N-Gram是大词汇连续语音识别中常用的一种语言模型，对中文而言，我们称之为汉语语言模型(CLM, Chinese Language Model)。汉语语言模型...

13430

38870

### 【算法】利用文档-词项矩阵实现文本数据结构化

“词袋模型”一词源自“Bag of words”，简称 BOW ，是构建文档-词项矩阵的基本思想。对于给定的文本，可以是一个段落，也可以是一个文档，该模型都忽略...

45170

30010

40780

### Tensorflow使用的预训练的resnet_v2_50，resnet_v2_101，resnet_v2_152等模型预测，训练

tensorflow 实现：Inception，ResNet ， VGG ， MobileNet， Inception-ResNet； 地址： https:/...

1.2K80

56640

293100

4K60