问题描述

一道题目，请大家帮帮忙，谢谢了

【问题描述】
　　小山田心子是一只快乐的小白兔，某天她看到一座彩虹桥，彩虹桥长度为N，每个单位都有一个美观度，小山田心子一开始在单位1，并取走单位1的美观值，接下来她会在从下一格开始到N中选择一个最大美观度的单位跳过去（如果美观值相同取前面的），然后取走美观值，直到她走到N，请输出她取走的美观度之和。
【输入格式】
　　第一行一个整数N（10<N<1000），接下来一行N个整数表示彩虹桥每个单位的美观度。
【输出格式】
　　小山田心子取过的美观值之和。

【输入样例1】
　　5
　　5 4 3 2 1
【输出样例1】
　　15

【输入样例2】
　　10
　　5 9 4 6 10 8 7 5 4 7
【输出样例2】
　　37

【样例解释】
　　样例1：（兔子一开始在单位1（取走美观度5），然后在2到5找最大，找到单位2的美观度4…一直找到单位N，美观度是15）；
　　样例2：（兔子先取单位1，在2到10中找最大找到单位5的美观度10，然后在6到10找最大找到单位6的美观度8，然后在7到10找最大找到单位7的美观度7，接下来在单位8到10找到单位10的美观度7，答案即为5+10+8+7+7=37）。

【数据范围】
　　N=200000（注意这里）
其中一个 n=200000 的数据点 http://pan.baidu.com/s/1o6qrs2A
感谢大神

解决方案

虽然是从前往后跳，但是感觉求值应该从后来算。你看哈，从最后一位开始，肯定是可以取到的，然后将这位作为flag，向前搜索。如果比flag小，则略过，如果大于flag，则计入总和，并更新flag。如此往前搜索，直到第一位，当然第一位也计入总和。这样复杂度也就是O(1)。题主琢磨下是否可行？

解决方案二：

有人吗……
感谢喽
在线等
立即采纳

解决方案三：

有人吗……
感谢喽
在线等
立即采纳

解决方案四：

public class N { public static int total(int[] a) { if (a == null || a.length == 0) { return 0; } int start = 1; int total = a[0]; while (true) { start = findLargest(start + 1, a); if (start >= a.length) { break; } total += a[start]; } return total; } public static int findLargest(int start, int[] a) { if (start >= a.length) { return start; } int max = a[start], position = start; for (int ix = start; ix < a.length; ix++) { if (a[ix] > max) { max = a[ix]; position = ix; } } return position; } public static void main(String[] args) { System.out.println(total(new int[]{5, 9, 4, 6, 10, 8, 7, 5, 4, 7})); }}

解决方案五：

#include
int main()
{

 int i,n,sum,j,temp;
 int a[1001];
 scanf("%d",&n);
 for (i=n-1;i>=0;i--)
    scanf("%d",&a[i]);
    sum=a[0]+a[n-1];
    i=1;
    temp=a[0];//开头和末尾一定是
    for (j=i;j<=n-2;j++)//比到之前一个因为第一个一定是
        if (a[j]>=temp)
        {
        sum=sum+a[j];//找到之前一个比它大的数
        temp=a[j];//更新最小值
        }

        printf("%dn",sum);
    return 0;

}

解决方案六：

<?php

$a = array(5, 9, 4, 6, 10, 8, 7, 5, 4, 7,);
$flag = $a[count($a)-1];
$sum = $a[0] + $a[count($a)-1];
for($i = count($a)-2; $i > 0; $i--){
if($a[$i] >= $flag){
$flag = $a[$i];
$sum += $a[$i];
}
}
echo $sum;exit;