最佳索引 - HackerEarth 解决方案，帮我优化代码

Question

问题链接：https://www.hackerearth.com/practice/basic-programming/input-output/basics-of-input-output/practice-problems/algorithm/best-index-1-45a2f8ff/

这里我用JAVA写了一段代码。 4 个测试用例正在通过，其余的由于时间限制而失败。帮我优化一下代码。还有其他方法可以接近吗？

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class TestClass {
    public static void main(String args[] ) throws Exception {
        
        Scanner sc = new Scanner(System.in);


        ArrayList<Integer> list = new ArrayList<>();


        int n = sc.nextInt();
        int[] arr = new int[n];

        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }

        list.add(0);
        for(int i=1;i<n; i++){
            int sum = list.get(i-1); ;
            list.add(sum+i);
        }

        int pos = 0;
        for(int i=0;i<list.size();i++){
            if(list.get(i)>n){
                pos = i-1;
                break;
            }
            else if(list.get(i)==n){
                pos = i;
                break;
            }
        }

        int len = n;
        int max = 0;
        for(int i=0; i< n;i++){
            int sum = 0;
            if(list.get(pos)>len){
                pos--;
            }
            for(int j=i;j<list.get(pos)+i;j++){
                sum = sum+arr[j];
            }
            len--;
            max = Math.max(max, sum);
        }
        System.out.println(max);
    }
}

Answer 1

O(n) 时间的解决方案。 （我的英语不好:)））

• 我的想法是：

• 您循环源数组以存储另一个具有规则的数组：

  newArr[i] = source[0] + source[1] +...+ source[i]

  Sum of element x -> y of source array = newArr[y] - newArr[x-1]

• 再次循环源数组：

  .) With index i:
      ..) if size - i % 3 == 0 then sum special = newArr[size-1] - newArr[i-1] (i < 0 then value is 0)
      ..) if size - i % 3 != 0 then sum special = newArr[size - i - (size - i) % 3] - newArr[i - 1]