最大子序列和问题的多种解法

1.O(n)的解法

/*
返回最大和
*/
int maxSum_1(const int A[], int n)
{int thisSum, maxSum;thisSum = maxSum = 0;for (int j = 0; j < n; ++j){thisSum += A[j];if (thisSum > maxSum){maxSum = thisSum;}else {if (thisSum < 0)thisSum = 0;}}return maxSum;
}//返回最大和，同时打印出子序列边界
int maxSum_2(const int A[], int n)
{int thisSum, maxSum;thisSum = maxSum = 0;int start,end;	int temps, tempe;start=end=temps = tempe = 0;for (int j = 0; j < n; ++j){//重置temps tempeif (thisSum == 0){tempe = temps = j;}thisSum += A[j];if (thisSum > maxSum){maxSum = thisSum;tempe = j;//更新start endstart = temps;end = tempe;}else {if (thisSum < 0)thisSum = 0;}}cout << start << " " << end << endl;return maxSum;
}

2.分治解法，O(NlogN)

算法思想：
最大子序列和可能在三处出现：

• 1.在整个数据序列的左半部分；
• 2.整个出现在右半部分；
• 3.出现在中间，跨越中部占据左右两部分

第三种情况可以通过求前半部分的最大和（包含前半部分最后一个元素） 以及 后半部分的最大和而得到（包含后半部分第一个元素）

int maxSum_3(const int A[], int left, int right)
{int maxLeftSum, maxRightSum;int maxLeftBorderSum, maxRightBorderSum;int leftBorderSum, rightBorderSum;int center;if (left == right)		//base case{if (A[left] > 0)return A[left];elsereturn 0;}center = (left + right) / 2;//第一种情况maxLeftSum = maxSum_3(A, left, center);//第二种情况maxRightSum = maxSum_3(A, center + 1, right);maxLeftBorderSum = 0;leftBorderSum = 0;//第三种情况for (int i = center; i >= left; --i){leftBorderSum += A[i];if (leftBorderSum > maxLeftBorderSum)maxLeftBorderSum = leftBorderSum;}maxRightBorderSum = 0; rightBorderSum = 0;for (int i = center + 1; i <= right; ++i){rightBorderSum += A[i];if (rightBorderSum > maxRightBorderSum)maxRightBorderSum = rightBorderSum;}return max({ maxLeftSum,maxRightSum,maxLeftBorderSum + maxRightBorderSum });
}

3.双重循环，O(N^2)

int maxSum_4(const int A[],int N)
{int thisSum,maxSum;maxSum=0;for(int i=0;i<N;++i){thisSum=0;for(int j=i;j<N;++j){thisSum+=A[j];if(thisSum>maxSum)maxSum=thisSum;}}return maxSum;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！