Sums of subarrays
Problem 663
Let be the tribonacci numbers defined as:
;
;
.
;
;
.
For a given integer , let be an array of length (indexed from 0 to ), that is initially filled with zeros.
The array is changed iteratively by replacing with in each step .
After each step , define to be , the maximal sum of any contiguous subarray of .
The array is changed iteratively by replacing with in each step .
After each step , define to be , the maximal sum of any contiguous subarray of .
The first 6 steps for are illustrated below:
Initial state:
Step 1: ,
Step 2: ,
Step 3: ,
Step 4: ,
Step 5: ,
Step 6: ,
Initial state:
Step 1: ,
Step 2: ,
Step 3: ,
Step 4: ,
Step 5: ,
Step 6: ,
Let . Thus .
You are given , and .
You are given , and .
Find .