|
First, we can always assume B>0; if not, just reverse the sequence. However, A *could* be negative... and everybody missed that!
IF A>0, then all numbers are positive, and the greatest sum is S= A(N+1) + BN(N+1)/2. In any case, since x+y and x-y have the same parity, the parity of the last result will be the same as the parity of S. HOWEVER!! If A<0, there are NEGATIVE numbers in the mix, you can achieve a larger S. For example, if A=-3, B=2, N=3, the numbers are -3, -1, 1 and 3. The first formula gives S=0, while you can do better: first subtract -3 from -1 (getting 2), and then sum all results, for a total of 6. The idea is: if A, A+B, ..., A+KB are all negative, you can get a higher result by first subtracting A+KB from A+(K
+1)B (getting B), then subtracting all the other negative terms from B, and then adding all positive terms. For example: if the sequence was -14, -11, -8, -5, -2, 1, 4, 7, 10, we would go: 1-(-2)=3; 3-(-5)=8; 8-(-8)=16; 16-(-11)=27; 27-(-14)=41; 41+4=45; 45+7=52; 52+10=62. The case with negatives needs more analysis! |
