1. 找出一個(gè)數(shù)組中，最大的一段連續(xù)的數(shù)的和。Find out the subarray which has the largest sum.
例如：[1, -3, 2, -4 , 5 , 6, -2, 6, 7] 最大的和就是 22 = 5 + 6 - 2 + 6 +7.
解法如下：
int subMax(int [] a)
{
int best = 0;
int sum = 0;
for(int i = 0; i < a.length; i++)
{
sum = sum + a[i];
if(sum < 0 )
sum = 0;
else if(sum > best)
best = sum;
}
return best;
}
想法就是一直加接下來的數(shù)，如果小于零就變?yōu)?，大于最大的數(shù)就更新。其中一點(diǎn)就是，如果遇到負(fù)數(shù)，
如果和不小于零就不用使sum為零。如果數(shù)組全部為負(fù)數(shù)，上面的代碼有點(diǎn)問題，但不改了。如果想知道
這個(gè)最大的和的序列是什么，只要稍微改變就可以了，不說了。
2.
Ugly Number: 找出第n個(gè)能被2，3，5整除的數(shù)
例如：2, 3, 4, 5, 6, 9,10, 12, 15, 20, 25 ... 第3個(gè)是4， 第4個(gè)是5，第5個(gè)是6 ... 第200是？
想法：首先是從 1開始，2，3，5分別乘1，最小的是2，接下來就是2，2的位置進(jìn)1，3和5的位置不變
再來一次，最小的是3，3的位置進(jìn)1，2和5位置進(jìn)1，再來一次，最小的是4，3和5的位置不變。。。
int uglyNum( int n)
{
int a = new int[n+1]
a[0] = 1;
int i2 = 0, i3 = 0, i5 = 0;
int n2 = 0; n3 = 0; n5 = 0;
int m = 0;
for(int i = 0; i <= n; i++)
{
n2 = a[i2] * 2;
n3 = a[i3] * 3;
n5 = a[i5] * 5;
m = min(n2, n3, n5);
if(m == n2)
{
a[i] = m;
i2++;
}
//similar for i3 and i5
}
return a[n];
}
3. 最后一個(gè)問題：給 i, j 兩個(gè)數(shù)，然后打印出 2^i ，5^j 的序列
例如： i = 3 j =4 就打印出：
2^0 * 5 ^0 = 1
2^1 * 5^0 = 2
2^2 * 5 ^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
...
解法：和上面一個(gè)解法很相似，不過注意要處理相等的情況，比如2 * 2^1 * 5 ^1 = 20 2^2 * 5^0 ^5 = 20,
代碼就不寫了。