- 基本思想：找出最优解所满足的形式（即必要条件），然后在这样的条件下通过搜索的方式找出最优解
- 首先，最优路径一定是先向左走到头（这里的头指的是最优解的边界），然后再向右走到头，最多转向一次，或者先向右走到头，然后再向左走到头，最多转向一次
- 设原点为 s t a r t P o s startPos startPos，以原点向左走的最大步数为 x x x,以原点向右走的最大步数为 y y y。
当采用前一种做法时原问题为：
求 [ s t a r t p o s − x , s t a r t p o s + y ] [startpos - x,startpos +y] [startpos−x,startpos+y]区间内水果的最大数目，在满足约束条件 2 x + y ≤ k 2x + y leq k 2x+y≤k， x ≤ y x leq y x≤y的条件下。
- 在给定 x x x的条件下，要使得区间尽量大，显然有 y = k − 2 x y = k - 2x y=k−2x
- 并且 x ≤ y x leq y x≤y，否则可以使用后一种做法（先向右走到尽头，再向左走到尽头）而使得步数k还没有用尽
原问题转换为：求得一个大于等于0得正整数 x x x使得区间 [ s t a r t p o s − x , s t a r t p o s + k − 2 x ] [startpos - x,startpos + k - 2x] [startpos−x,startpos+k−2x]中水果数目达到最大值。
- 并且需要满足 k − 2 x ≥ 0 , x ≥ 0 ， 3 x ≤ k k - 2x geq 0,x geq 0，3x leq k k−2x≥0,x≥0，3x≤k,由于第一个不等式必须成立，且注意到整数，因此约束条件为 0 ≤ x ≤ ⌊ k / 3 ⌋ 0leq x leq lfloor k/3 rfloor 0≤x≤⌊k/3⌋
- 在这个区间上执行搜索
x
x
x，找到最优的
x
x
x对应的值即可得到结果。
- 可在最大数据范围内维护数轴的前缀和即可实现, p r e [ i ] 表 示 截 止 i 位 置 的 pre[i]表示截止i位置的 pre[i]表示截止i位置的所有水果个数。欲求任意区间的数值可直接用两个前缀和详见即可
当采用后一种做法时原问题为：
求
[
s
t
a
r
t
p
o
s
−
x
,
s
t
a
r
t
p
o
s
+
y
]
[startpos - x,startpos +y]
[startpos−x,startpos+y]区间内水果的最大数目，在满足约束条件
x
+
2
y
≤
k
x + 2y leq k
x+2y≤k，
x
>
=
y
x >=y
x>=y的条件下。
- 即： 求 [ s t a r t p o s − k + 2 y , s t a r t p o s + y ] [startpos - k + 2y,startpos +y] [startpos−k+2y,startpos+y]区间内水果的最大数目，在满足约束条件 0 ≤ y < = ⌊ k / 3 ⌋ 0leq y<= lfloor k/3rfloor 0≤y<=⌊k/3⌋的条件下
class Solution {
public int maxTotalFruits(int[][] fruits, int startPos, int k) {
int[] pre = new int[200001]; //保存前缀和
//统计前缀和
int i ;
int next ;
if(fruits[0][0] == 0)
{
pre[0] = fruits[0][1];
next = 1;
}
else
{
pre[0] = next = 0;
}
for(i = 1;i= 200000?pre[200000] : pre[startPos + k - 2*x];
ans = Math.max(ans,upper - lower);
}
for(int y = 0;y<=k/3;y++)
{
int lower = startPos - k + 2*y<=0?0:pre[startPos - k + 2*y - 1];
int upper = startPos + y>=200000?pre[200000]:pre[startPos + y];
ans = Math.max(ans,upper - lower);
}
return ans;
}
}
