日期：2016年11月7日

分析求子数组最大值问题

求子数组的最大值是一道经典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]起，newsum和max均为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);