Best Index - HackerEarth Solution, help me optimize the code

Question

I am trying to solve HackerEarth problem Best Index:

Problem

You are given an array or elements. Now you need to choose the best index of this array . An index of the array is called best if the special sum of this index is maximum across the special sum of all the other indices.

To calculate the special sum for any index , you pick the first element that is [] and add it to your sum. Now you pick next two elements i.e. [+1] and [+2] and add both of them to your sum. Now you will pick the next 3 elements and this continues till the index for which it is possible to pick the elements. For example:

If our array contains 10 elements and you choose index to be 3 then your special sum is denoted by -

([3]) + ([4] + [5]) + ([6] + [7] + [8]), beyond this it's not possible to add further elements as the index value will cross the value 10.

Find the best index and in the output print its corresponding special sum. Note that there may be more than one best indices but you need to only print the maximum special sum.

Input

First line contains an integer as input. Next line contains space separated integers denoting the elements of the array .

Output

In the output you have to print an integer that denotes the maximum special sum

Constraints

• 1 ≤ ≤ 10⁵
• −10⁷ ≤ [] ≤ 10⁷

Here I wrote code in Java. Four test cases are getting passed and the remaining are getting failed due to the time limit. How can I optimize the code? Is there another approach?

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

Solution with O(n) time. (My English is not good :)) )

• My idea is:

• You loop over source array to store an another array with rule:

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

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

• You loop over source array again:

  .) 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]
  

Answer 2

You could work from the right end of the input array to the left. Then the sum can be incrementally be adjusted, while you also keep track of the sum of the end of the array that is currently not included in the sum. When you know a next chunk can be added to the sum, you have that chunk ready. Add it and reset the sum for that unused part, ...Etc.

Here is an implementation:

class TestClass {
    public static int[] getArray() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        return arr;
    }

    public static long solve(int[] arr) {
        int n = arr.length;
        long result = arr[n - 1];
        long sum = 0, incomplete = 0;
        int j = n - 1;
        int k = n - 3; // Index at which a chunk can be added to the sum
        for (int i = n - 1; i >= 0; i--) {
            sum += arr[i];
            result = Math.max(result, sum);
            sum -= arr[j];
            incomplete += arr[j];
            j--;
            if (j == k) {
                k--;
                sum += incomplete;
                incomplete = 0;
                j = n - 1;
            }
        }
        return result;
    }

    public static void main(String args[] ) throws Exception {
        System.out.println(solve(getArray()));
    }
}