我的站点

一个系统软件工程师的随手涂鸦

Date: 十一月 7, 2016

分析求子数组最大值问题

求子数组的最大值是一道经典dynamic programming题,解法如下(参考这里):

public int maxSubArray(int[] A) {
   int newsum=A[0];
   int max=A[0];
   for(int i=1;i<A.length;i++){
       newsum=Math.max(newsum+A[i],A[i]);
       max= Math.max(max, newsum);
   }
   return max;
}

理解这个算法的关键在于:求出数组中以每个元素为子数组的最后一个元素的最大值(上述代码中newsum),这些最大值中的最大者即为解(上述代码中max)。分析如下:从第一个元素A[0]起,newsummax均为A[0]。而对下一个元素A[1],以A[1]为子数组的最后一个元素的最大值或者是A[0]+A[1]A[0]大于0),或是A[1],取两者最大值。接下来再看A[2],以A[2]为子数组的最后一个元素的最大值是A[0]+A[1]+A[2]A[1]+A[2]A[2]三者之间的最大值。以此类推。。。

C语言中使用scanf的一些注意事项

(1)scanf读取double类型数据应该使用%lf;而使用printf打印double时,要注意%lf用在printf中是C99才支持的,因此如果编译器不支持C99则要使用%f

double d;
scanf("%lf", &d);
printf("%f", d);

参考资料:
Reading in double values with scanf in c
Why does scanf() need “%lf” for doubles, when printf() is okay with just “%f”?

(2)

char str[10];
scanf ("%[^\n]%*c", str);

%[^\n]含义是从stdin读取输入保存到str,直到遇到第一个\n;而%*c则丢弃掉这个\n
参考资料:
scanf: “%[^\n]” skips the 2nd input but “ %[^\n]” does not. why?
What does scanf(“%*[^\n]%*c”) mean?

(3)限制输入字符串的长度,预留结尾的NUL

char str[10]
scanf("%9s", str);

Powered by WordPress & Theme by Anders Norén