欠伸展肢体，吟咏心自愉。这篇文章主要讲述数据结构 happiness相关的知识，希望能为你提供帮助。
问题描述
这一天是小 V 的生日，他收到了朋友们送给他的礼物。
现在，小 V 有 n 件礼物，他将这 n 件礼物排成一排，依次编号为 1 到 n，每件礼物都有
一个满意值 w[i]。
现在小 V 要从中选取连续编号的礼物（即选取[l, r]内的礼物），使得获得的 happiness 最
大。
[l, r]内的 happiness 定义为：
（[l, r]内所有礼物满意值的最小值） *（[l, r]内所有礼物满意值的和）
小 V 想知道他能获得的 happiness 最大是多少，你能帮帮他吗？
★数据输入
第一行为一个正整数 n。
第二行为 n 个整数 w[1], w[2], …, w[n]
其中：
对于 50%的数据： 1<
=n<
=100, 0<
=w[i]<
=100
对于 80%的数据： 1<
=n<
=1,000, 0<
=w[i]<
=1,000
对于 100%的数据： 1<
=n<
=100,000, 0<
=w[i]<
=10,000
★数据输出
小 V 能获得的最大 happiness 值。
★样例
输入
3
1 2 3
输出
10
输入
3
2 1 3
输出
9
解题思路
暴力
以每一个数为起点，向两边扩展，扩展到 比它小的数 或者 数组边界 停止。拓展过程统计sum
作为起点的数就是这一段数的最小值
用(sum*作为起点的数)更新最终的答案max_happiness
code
1 #include < stdio.h> 2 #include < stdlib.h> 3 4 int main() 5 { 6int i,j,k; 7int n; 8scanf("%d",& n); 9int *p = (int *)malloc(sizeof(int)*n); 10for(i=0; i< n; i++) 11scanf("%d",p+i); 12//------------------------------------- 13__int64 maxhap=0; 14 15for(i=0; i< n; i++) 16{ 17__int64 sum=0; 18for(j=i-1; j> =0& & p[j]> =p[i]; j--) 19sum+=p[j]; 20for(k=i; k< n& & p[k]> =p[i]; k++) 21sum+=p[k]; 22maxhap = sum*p[i]> maxhap ? sum*p[i] : maxhap; 23} 24printf("%I64d",maxhap); 25//------------------------------------- 26free(p); 27return 0; 28 }
【数据结构 happiness】
