A Bird and Fruit Trees

There are n trees in a circle. Each tree has a fruit value associated with it. A bird can sit on a tree for 0.5 sec and then he has to move to a neighbouring tree. It takes the bird 0.5 seconds to move from one tree to another. The bird gets the fruit value when she sits on a tree. We are given n number of seconds the bird has and, the fruit values val[m] of the trees. We have to maximise the total fruit value that the bird can gather. The bird can start from any tree.


Naive Thinking: 第一眼觉得是DP，但是写了写发现只要找到连续的相加之和最大的树群就行了，每棵树用的时间是固定的。

算法复杂度是O(n)。

 public class Solution{

    public static void main(String args[]){
        int val[] = {1,1,1,1,1,1,1,2,1,1,2,4};
        Solution s = new Solution();
        System.out.println(s.maxFruitValue(4,val));
    }

    public int maxFruitValue(int n, int val[]){
        int sum = 0;
        int max = 0;
        int begin = 0;
        int end = n;
        for(int i = 0;i < end && i < val.length;i++)
            sum += val[i];
        max = sum;
        if(n >= val.length){return max;}
        while(begin < val.length){
            sum -= val[begin++];
            sum += val[end];
            max = Math.max(max,sum);
            end = (end+1)%val.length;
        }
        return max;
    }
}