奶牛们的牧场

xchief

请问奶牛们的牧场，到底是个什么意思，既然说是连续的，为什么可以有负的，那要几个负的才算不是连续的？

青春年少的我们

xchief 发表于 2014-7-14 17:58
就是这个，有几块负的才算不是连续的

题目问的是输出这几块草地的肥沃程度和，你算负的没用                                            从头开始扫描，计算从起点（不一定是原点）到当前的累加和， 并维持最大的累加和值，如果累加和值为负，就放弃前面所有的数，从下一个位置从新当成起点重新开始。最后的维持的最大和值就是答案。

青春年少的我们

在一片辽阔无边的草地中，奶牛们要选择自己的牧场。 这一片草地可分为n块，每一块草的肥沃度都有所不同。 奶牛们希望能找出一些连续的、肥沃程度和最大的草地作为她们自己的牧场。 例如：有10块草地，每块草地的肥沃程度为 8 -9 2 7 6 -3 8 -10 6 2 那么肥沃程度最大的连续的草地是2 7 6 -3 8，选用这几块草地作为牧场，显然最明智的，肥沃程度之和达到了20。 现在有1000块草地，请你找出连续的的肥沃程度之和最大的来牧场来，请输出最大的牧场的肥沃程度之和。(请无视空行)： 88 16 78 40 46 85 3 98 20 32 94 88 0 18 29 2 54 -3 2 0 10 25 9 45 51 -40 68 16 -28 40 41 60 25 60 50 -4 60 -6 -10 24 71 54 92 66 -18 24 -8 76 43 45 10 4 55 48 -70 84 40 82 -65 86 99 32 9 11 49 40 -76 84 4 6 92 29 -78 35 60 31 -32 -39 -81 52 53 0 -85 92 -50 70 98 -20 18 -50 -28 -84 69 -25 -54 17 0 90 -56 0 78 34 60 18 75 50 62 74 39 61 88 0 -3 66 35 60 -61 -29 90 72 94 21 16 0 40 91 0 67 80 -40 -26 85 32 36 95 90 -12 -36 32 5 -97 79 32 48 77 -78 8 90 -75 64 90 60 -32 75 21 35 0 34 36 92 88 -93 -4 -68 35 -16 68 56 42 -10 -41 0 96 20 68 0 -82 42 25 52 44 -70 60 -62 56 -40 83 -49 49 0 12 64 0 -60 93 -61 93 -33 32 -1 76 40 6 97 -40 -40 -56 74 11 68 36 -90 0 0 98 87 30 52 62 80 -68 6 0 74 28 15 8 98 52 93 50 34 -24 -68 -49 72 56 -75 -75 50 16 8 0 16 25 17 22 98 30 28 62 -12 48 64 20 16 26 71 8 52 0 0 5 75 80 -61 40 -40 32 -60 36 40 -14 98 -42 0 77 56 36 -65 19 8 52 -20 52 -40 42 -19 78 0 25 7 77 16 25 60 -30 48 -82 80 14 24 48 70 25 65 -20 8 16 32 15 40 69 87 40 -29 56 36 -82 64 72 4 -80 72 2 -30 -32 18 88 95 59 76 2 36 96 0 28 92 43 -15 64 68 6 16 92 64 -20 0 -45 -25 -36 14 94 -4 40 72 82 -48 10 -49 34 68 80 -10 75 36 30 68 0 42 44 50 -60 37 66 10 45 45 66 -4 57 25 80 84 90 28 20 8 14 8 60 8 2 79 76 53 44 19 80 84 61 65 85 93 5 47 -55 24 40 39 46 5 18 0 32 0 -27 4 60 -40 66 18 60 60 96 52 70 23 76 0 18 86 94 52 49 76 37 98 68 -50 72 -86 48 -50 95 9 0 -52 33 63 28 -60 48 28 0 64 6 -36 96 12 24 0 82 -50 -80 54 66 20 -81 0 96 64 48 -65 -24 96 -8 -32 -40 -40 -92 90 48 12 84 91 -76 25 81 15 77 69 -4 -93 39 -76 65 -48 85 80 -54 81 88-87 70 50 -98 98 33 72 -73 5 94 -90 2 -28 -4 0 70 28 0 -68 -38 12 20 60 8 68 34 80 70 -40 47 2 -18 0 16 -10 49 55 92 62 -91 -30 12 88 73 40 82 -74 1 26 72 40 46 20 0 60 72 -16 -8 61 -62 4 59 0 -3 -32 38 -84 -48 30 72 86 80 66 28 64 -60 -25 80 64 93 -55 17 23 -52 79 84 73 80 50 93 75 44 65 88 -40 84 22 70 55 60 90 0 -41-88 32 40 -50 96 20 0 9 50 -38 -80 -90 34 94 -79 80 -40 -68 -88 36 75 -68 -20 0 92 -15 -80 28 -95 68 44 0 -24 59 35 93 51 -14 -65 32 74 70 -28 68 83 57 76 50 78 10 32 88 39 72 88 0 48 20 97 4 -40 -38 30 -84 -20 50 10 70 0 -98 2 8 -60 24 14 -44 76 85 -82 -92 55 -57 0 68 -85 24 -30 0 20 36 72 22 76 90 18 -67 -37 20 38 30 80 -76 18 0 -16 80 -35 40 92 -13 87 -24 54 98 35 48 18 67 32-56 44 48 76 39 56 -82 -23 28 10 32 64 64 80 88 40 -10 8 29 64 22 -8 -75 91 -66 75 -99 32 -68 8 20 24 85 -96 97 91 75 50 85 14 34 -32 80 0 13 -33 69 -80 92 -75 -74 0 -54 -30 96 40 40 11 29 86 40 -18 7 18 60 -95 -6 25 85 55 -50 64 38 -25 -32 -20 57 -44 64 -54 36 -40 -63 73 73 24 -16 20 40 -68 -43 6 69 0 -28 -45 -40 3 52 75 44 50 -60 72 24 -90 56 96 20 44 11 0 28 90 60 16 55 72 76 91 80 20 -80 30 5 76 94 51 76 -90 50 9 61 47 -45 -46 -45 0 4 40 -70 71 -34 0 30 19 56 -57 10 90 0 75 -86 42 50 88 -31 68 76 -36 0 -20 -8 -32 75 95 88 -75 0 28 -60 59 62 34 8 90 78 22 12 0 82 30 41 50 22 0 -80 -90 80 80 76 23 84 52 7 37 44 0 -10 44 66 40 26 -68 44 60 91 60 19 0 66 -84 20 40 80 -38 50 0 32 80 20 5 48 0 -69 60 11 78 44 30 48 -62 40 -42 56 98 -14 74 49 14 86 75 68 0 44 2 -60 21 -68 38 44 54 60 60 68 23 98 70 -18 83 80 52 -52 -10 -36 -35 25 40 81 -32 72 88 65 -9 4请你帮奶牛们找到他们的牧场，输出这几块草地的肥沃程度和。                                                               是这个吗？

青春年少的我们

从头开始扫描，计算从起点（不一定是原点）到当前的累加和， 并维持最大的累加和值，如果累加和值为负，就放弃前面所有的数，从下一个位置从新当成起点重新开始。最后的维持的最大和值就是答案。

xchief

青春年少的我们 发表于 2014-7-14 17:56
在一片辽阔无边的草地中，奶牛们要选择自己的牧场。 这一片草地可分为n块，每一块草的肥沃度都有所不同。  ...

就是这个，有几块负的才算不是连续的

xchief

青春年少的我们 发表于 2014-7-14 17:56
从头开始扫描，计算从起点（不一定是原点）到当前的累加和， 并维持最大的累加和值，如果累加和值为负，就 ...

就是说可以有N个负的！只考虑和值！

rosynirvana

连续和正负无关
就是求序列中的一个子序列，让这个子序列的和最大化

xchief

rosynirvana 发表于 2014-7-14 18:12
连续和正负无关
就是求序列中的一个子序列，让这个子序列的和最大化

你能不能加我抠抠

xchief

{:soso_e136:}那这样的话，这题一点也不难！我通过了