Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

自己做出来的,感觉好开心……附代码和讲解,O(n)的算法……做不出来再看哦

Posted by 1200017623 at 2013-01-30 18:00:39 on Problem 2479
改进的关键在于求nFrom的算法。
    考虑到其中的状态转化方程:nFrom[i] = max{nFrom[i + 1] , max{Sum[i][k]  | i <= k && k < n}};如果要求出所有的Sum[i][k]再比较,必将产生O(n^2)的时间复杂度,而这是不允许的。
   如果换一种思路:为什么不直接将maxSum作为一个变量加以研究呢?事实上,如果令Smax[i] = max{Sum[i][k]  | i <= k && k < n},那么考虑i-1的情况:
   Smax[i - 1] = max{Sum[i - 1][k] |  i -1<= k && k < n}
             = max{Sum[i - 1][i -1],  max {Sum[i-1][k] | i <= k}}
             =max{nArray[i-1][i-1], nArray[i-1][i-1] + Smax[i]};
   这样一来,问题就迎刃而解了……时间复杂度成功降至O(n)


Here's my Source Code:<C++ Memory: 1336 K  Time: 172ms>

#include<iostream>
using namespace std;

const int MAX = 50005;
const int MIN = -2147483647;
static int nArray[MAX] = {0};
//The biggest-sum sequence from a[i]/ to a[i]
static int nFrom[MAX] = {0},nTo[MAX] = {0};

int main(){
	int nCount,n,nTempMax,nMax;
	scanf("%d",&nCount);
	for(;nCount > 0;--nCount){
		scanf("%d",&n);
		nMax = MIN;
		for(int i = 0;i < n;++i){
			scanf("%d",&nArray[i]);
		}
		nTo[0] = nArray[0];
		nFrom[n - 1] = nArray[n - 1];

		/* Get the nTo[i] */
		nTempMax = nArray[0];
		for(int i = 1;i < n;++i){
			//The highest sum to i is max(highest[i-1],nTempMax(include i))  )
			nTempMax = nTempMax > 0 ? nTempMax + nArray[i] : nArray[i];
			nTo[i] = nTo[i-1] > nTempMax ? nTo[i-1] : nTempMax;
		}

		/* Get the nFrom[i] */
		nTempMax = nArray[n-1];
		for(int i = n - 2;i >= 0;--i){
			nTempMax = nTempMax > 0 ? nTempMax + nArray[i] : nArray[i];
			nFrom[i] = nFrom[i+1] > nTempMax ? nFrom[i+1] : nTempMax;
		}
		for(int i = 0;i < n - 1;++i){
			nMax = nTo[i] + nFrom[i+1] > nMax ? nTo[i] + nFrom[i+1] : nMax;
		}
		printf("%d\n",nMax);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator