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

### 算法一：穷举式地尝试所有的可能

```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）策略

#### 分治策略：

：把问题分成若干个（通常是两个）规模相当的子问题，然后递归地对它们求解。 ：将若干个问题的解4合并到一起并可能再做少量的附加工作，最后得到整个问题的解。

```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;
}```

38 篇文章38 人订阅

0 条评论

## 相关文章

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

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

37360

### 02 The TensorFlow Way（1）

The TensorFlow Way Introduction：          现在我们介绍了TensorFlow如何创建张量，使用变量和占位符，我们将介...

227100

29310

### n-gram

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

13330

531110

18940

218100

15530

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

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

45070

38670