Question

In: Computer Science

We have an array of numbers, and we start at index 0. At every point, we're...

We have an array of numbers, and we start at index 0.

At every point, we're allowed to jump from index i to i+3, i+4, or stop where we are.

We'd like to find the maximum possible sum of the numbers we visit.

For example, for the array [14, 28, 79, -87, 29, 34, -7, 65, -11, 91, 32, 27, -5], the answer is 140.

(starting at the 14, we jump 4 spots to 29, then 3 spots to 65, another 3 to 32, then stop. 14 + 29 + 65 + 32 = 140)

What's the maximum possible sum we could visit for this array:

[95, 69, 68, 44, 0, 53, 34, -83, -8, 38, -63, -89, 34, -91, 1, 39, -7, -54, 85, -25, -47, 89, -57, -18, -22, -50, -74, -91, -38, 99, 73, 7, 44, -47, -35, -70, 26, -54, -28, 7, -26, -73, -48, -76, -18, 94, -54, 65, -71, -10, 5, 64, 55, 68, 7, 41, -52, 57, -75, 90, -21, -47, -88, -5, -9, 46, -8, 71, 34, 82, 10, -37, 37, 1, 49, 91, 80, 57, -56, 83, -58, 24, -34, 30, -65, 42, -28, -84, -58, -62, 20, 89, -43, -16, 9, 37, -21, -71, -27, 93, 93, 3, 24, 51, 19, -54, -20, 43, 96, 15, -4, -30, -12, -88, 95, -89, 63, 63, 26, 34, 9, 66, 40, 59, -69, -29, -3, -89, -58, 45, 68, 45, 92, -51, 89, -75, 0, 14, 46, -20, -90, -83, 82, 29, -32, 68, 55, 41, -85, 56, 97, -11, -25, -28, 65, 61, 54, -36, -24, 98, 49, 19, 3, -94, -46, 26, 92, -72, -29, 93, 71, 15, 3, -89, -66, -85, -42, 83, 43, 27, 76, 71, 62, 44, 9, 2, 40, 8, 78, -6, -61, -93, 28, -46, -48, 25, -34, -91, 73, 90, 77, -5, 98, 1, -5, -85, 63, -15, 57, 20, 71, -67, -60, -46, -71, -9, 62, 99, 80, -15, 53, 29, 52, -91, -78, -77, -57, 21, -74, 46, -11, 74, -21, -48, -7, -56, 54, 8, -51, -61, -46, 79, 42, 97, 61, 40, -99, -13, 55, -53, -71, 80, 31, -35, 77, 89, -2, 75, 59, -66, 87, 23, 48, 80, -28, 86, 54, 37, -41, 95, -87, 79, -49, 8, -95, 66, 79, -38, 75, 49, -30, 7, -46, -44, 43, -26, -63, 23, 77, -8, 36, 83, 10, 12, -34, 32, -63, -32, 47, -5, 53, 66, 32, 14, 24, 28, 57, -48, -89, -51, -26, -21, -37, -41, -17, -40, 19, 25, 89, -11, 92, -43, -50, 53, -36, 50, -12, 68, -28, 18, 62, -48, -86, 87, -80, 58, 73, -93, 81, -86, 26, 3, 51, 74, 37, 45, 85, 12, 49, 93, -93, -5, 61, -64, -48, -11, 68, -36, -83, -18, 30, -53, -88, 6, 43, -38, 50, -28, 91, 49, 21, 86, -15, -18, 2, 0, 55, -73, 85, -49, -18, -90, 89, 79, -21, 23, 38, 43, 83, 72, 63, 14, -35, 81, -2, -71, 70, 51, -26, -20, 74, 10, -37, 61, -29, -62, 18, -46, 75, 98, 18, -4, 25, 13, 70, -34, 79, 16, -55, -7, -56, -55, 79, 29, 13, -31, -12, -29, -33, 12, 17, -5, -59, -12, 76, -6, -4, -5, -90, -45, -33, -14, -56, 64, -99, -65, -98, -97, 35, -50, -63, 8, -7, -46, 3, -69, 24, -23, -6, 78, -21, 2, -99, -29, 75, 40, -30, -40, 10, -41, -65, -42, -88, -8, -32, -2, -39, -95, -73, 32, 99, -35, -88, 81, -32, -19, 58, 83, -73, -23, 1, -34, -40, -39, 35, -52, -24, 57, -44, 2]

Solutions

Expert Solution

Answer is 6510

Program Code Screenshot :

Sample Output :

Program Code to Copy

class Main{

    public static int max(int... arr){
        int mx = arr[0];
        for(int a : arr){
            mx = Math.max(mx,a);
        }
        return mx;
    }

    public static void main(String[] args) {
        int arr[] = {95, 69, 68, 44, 0, 53, 34, -83, -8, 38, -63, -89, 34, -91, 1, 39, -7, -54, 85, -25, -47, 89, -57, -18, -22, -50, -74, -91, -38, 99, 73, 7, 44, -47, -35, -70, 26, -54, -28, 7, -26, -73, -48, -76, -18, 94, -54, 65, -71, -10, 5, 64, 55,
                68, 7, 41, -52, 57, -75, 90, -21, -47, -88, -5, -9, 46, -8, 71, 34, 82, 10, -37, 37, 1, 49, 91, 80, 57, -56, 83, -58, 24, -34, 30, -65, 42, -28, -84, -58, -62, 20, 89, -43, -16, 9, 37, -21, -71, -27, 93, 93, 3, 24, 51, 19, -54, -20, 43,
                96, 15, -4, -30, -12, -88, 95, -89, 63, 63, 26, 34, 9, 66, 40, 59, -69, -29, -3, -89, -58, 45, 68, 45, 92, -51, 89, -75, 0, 14, 46, -20, -90, -83, 82, 29, -32, 68, 55, 41, -85, 56, 97, -11, -25, -28, 65, 61, 54, -36, -24, 98, 49, 19,
                3, -94, -46, 26, 92, -72, -29, 93, 71, 15, 3, -89, -66, -85, -42, 83, 43, 27, 76, 71, 62, 44, 9, 2, 40, 8, 78, -6, -61, -93, 28, -46, -48, 25, -34, -91, 73, 90, 77, -5, 98, 1, -5, -85, 63, -15, 57, 20, 71, -67, -60, -46, -71, -9, 62,
                99, 80, -15, 53, 29, 52, -91, -78, -77, -57, 21, -74, 46, -11, 74, -21, -48, -7, -56, 54, 8, -51, -61, -46, 79, 42, 97, 61, 40, -99, -13, 55, -53, -71, 80, 31, -35, 77, 89, -2, 75, 59, -66, 87, 23, 48, 80, -28, 86, 54, 37, -41, 95,
                -87, 79, -49, 8, -95, 66, 79, -38, 75, 49, -30, 7, -46, -44, 43, -26, -63, 23, 77, -8, 36, 83, 10, 12, -34, 32, -63, -32, 47, -5, 53, 66, 32, 14, 24, 28, 57, -48, -89, -51, -26, -21, -37, -41, -17, -40, 19, 25, 89, -11, 92, -43, -50,
                53, -36, 50, -12, 68, -28, 18, 62, -48, -86, 87, -80, 58, 73, -93, 81, -86, 26, 3, 51, 74, 37, 45, 85, 12, 49, 93, -93, -5, 61, -64, -48, -11, 68, -36, -83, -18, 30, -53, -88, 6, 43, -38, 50, -28, 91, 49, 21, 86, -15, -18, 2, 0, 55,
                -73, 85, -49, -18, -90, 89, 79, -21, 23, 38, 43, 83, 72, 63, 14, -35, 81, -2, -71, 70, 51, -26, -20, 74, 10, -37, 61, -29, -62, 18, -46, 75, 98, 18, -4, 25, 13, 70, -34, 79, 16, -55, -7, -56, -55, 79, 29, 13, -31, -12, -29, -33,
                12, 17, -5, -59, -12, 76, -6, -4, -5, -90, -45, -33, -14, -56, 64, -99, -65, -98, -97, 35, -50, -63, 8, -7, -46, 3, -69, 24, -23, -6, 78, -21, 2, -99, -29, 75, 40, -30, -40, 10, -41, -65, -42, -88, -8, -32, -2, -39, -95, -73, 32,
                99, -35, -88, 81, -32, -19, 58, 83, -73, -23, 1, -34, -40, -39, 35, -52, -24, 57, -44, 2};
        //Initialize an array to store dp
        int dp[] = new int[arr.length];
        //Initialize answer for the last element
        dp[arr.length-1] = Math.max(arr[arr.length-1],0);
        for(int i=arr.length-2;i>=0;i--){
            //Build dp array
            dp[i] = max(0,arr[i]+((i+3)<dp.length?dp[i+3]:0),arr[i]+((i+4)<dp.length?dp[i+4]:0));
        }
        //Print first answer
        System.out.println(dp[0]);

    }
}

venereology answered 2 weeks ago
Next > < Previous

Related Solutions

Given an array of numbers, find the index of the smallest array element (the pivot), for...
Given an array of numbers, find the index of the smallest array element (the pivot), for which the sums of all elements to the left and to the right are equal. The array may not be reordered. Example arr=[1,2,3,4,6] the sum of the first three elements, 1+2+3=6. The value of the last element is 6. Using zero based indexing, arr[3]=4 is the pivot between the two subarrays. The index of the pivot is 3. Function Description Complete the function balancedSum...
Suppose we have an array A that contains a prime numbers from 2 to 200 in...
Suppose we have an array A that contains a prime numbers from 2 to 200 in sorted order. How many items of the array A would the binary search algorithm have to examine before concluding that 60 is not in the array A? 30 200 100 6 2- Suppose we have an array that contains 182 village name. These names are sorted alphabetically. How many names would binary search algorithm examine to locate a particular name in the array, in...
How would you take a given array of non-repeating random integers and sort every 5th element. Meaning index 0 is the smallest element in the array.
JAVA ProgrammingHow would you take a given array of non-repeating random integers and sort every 5th element. Meaning index 0 is the smallest element in the array. index 4 is the 5th smallest element in the array, index 9 is the 10th smallest element in the array and so on...- this array could be small (like 5 indexes) or large (like 100,000 indexes).- all other numbers do not change position
Given an array A of n distinct real numbers, we say that a pair of numbers...
Given an array A of n distinct real numbers, we say that a pair of numbers i, j ∈ {0, . . . , n−1} form an inversion of A if i < j and A[i] > A[j]. Let inv(A) = {(i, j) | i < j and A[i] > A[j]}. Answer the following: (a) How small can the number of inversions be? Give an example of an array of length n with the smallest possible number of inversions. (b)...
Given an array A of n distinct numbers, we say that a pair of numbers i,...
Given an array A of n distinct numbers, we say that a pair of numbers i, j ∈ {0, . . . , n − 1} form an inversion of A if i < j and A[i] > A[j]. Let inv(A) = {(i, j) | i < j and A[i] > A[j]}. Define the Inversion problem as follows: • Input: an array A consisting of distinct numbers. • Output: the number of inversions of A, i.e. |inv(A)|. Answer the following:...
Create a class called “Array” that implements a fixed-sized two-dimensional array of floating-point numbers.
Programing in Scala language: Create a class called “Array” that implements a fixed-sized two-dimensional array of floating-point numbers. Write separate methods to get an element (given parametersrow and col), set an element (given parametersrow, col, and value), and output the matrix to the console formatted properly in rows and columns. Next, provide an immutable method to perform array addition given two same-sized array.
Suppose that all the numbers in an array are located in an interval [0,12], and we...
Suppose that all the numbers in an array are located in an interval [0,12], and we need to find the largest element with accuracy ε = 0.8. How many iterations will you need if we use the quantum optimization algorithm? How many times do we need to apply Grover's algorithm? Trace the quantum optimization algorithm for the case when the actual largest element is a5 = 3.14
Q1. We have a controller, and every time the Operator changes the Set Point, the controller...
Q1. We have a controller, and every time the Operator changes the Set Point, the controller responds, and gets the process sorted out. Now, somewhere, we have read that load disturbances needed to be considered in processes, as well. How will this controller react, if there is a load disturbance, and not a Set Point change?                                                                                                                        Q3. The Process Variable jumps around, quite a bit. Which of the PID settings should we not be using, to improve controllability, and...
We have a controller, and every time the Operator changes the Set Point, the controller responds,...
We have a controller, and every time the Operator changes the Set Point, the controller responds, and gets the process sorted out. Now, somewhere, we have read that load disturbances needed to be considered in processes, as well. How will this controller react, if there is a load disturbance, and not a Set Point change? provide a basic answer to this.
Given an array A[1..n] of integers - all of whose numbers are in the range [0,...
Given an array A[1..n] of integers - all of whose numbers are in the range [0, n^3 − 1] give an algorithm which sorts them in O(n) time.
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT