UVa 507 Jill Rides Again

Minimum Subarray Sum
想法：
    這題求最大MSS值的區間，注意output說明，如果MSS一樣的話，要選擇最大的區間長度(j-i盡可能大)，如果區間長度又一樣長的話，那麼要選擇先出現的那個。

• 區間長度盡可能大：第18行要用">="
• 選擇最大區間長度：第24行的判斷式

	#include <cstdio>
	using namespace std;
	int num[20001];
	int main()
	{
	int Case, S;
	scanf("%d", &Case);
	for (int i = 1; i <= Case; ++i)
	{
	int num, MSS = -1, Start = -1, End = -1;
	int Max = 0, Max_Start, Max_End;
	scanf("%d", &S);
	for (int j = 1; j <= S - 1; ++j){
	scanf("%d", &num);
	if (MSS >= 0)
	MSS += num;
	else {
	MSS = num;
	Start = j;
	}
	if (MSS > Max ||
	(MSS == Max && j+1 - Start > Max_End - Max_Start))
	{
	Max = MSS;
	Max_Start = Start;
	Max_End = j + 1;
	}
	}
	if (Max == 0)
	printf("Route %d has no nice parts\n", i);
	else
	printf("The nicest part of route %d is between stops %d and %d\n", i, Max_Start, Max_End);
	}
	}

view raw [UVa] 507 Jill Rides Again.cpp hosted with ❤ by GitHub