Please answer all question C++

1

Write a program that takes in a square matrix of integers and outputs the largest sub-square-matrix sum.

The first line of input is an integer which indicates the dimension of the square matrix, followed by the actual matrix row-by-row.

Input: 3

1 2 3

4 5 6

7 8 9

Output: 45

Input: 3

1 2 3

4 5 6

-7 -8 -9

Output: 16

NB: Since the largest square matrix is [2 3; 5 6] which sums to 16

Hint: Derive your algorithm from Kadanes Algorithm from Analysis of Algorithms Lab

2.

Suppose you are trying to bind many books together (for whatever reason you can think of).

The books may consist of a different number of pages. For example, Book A can have 12 pages and Book B can have 500 pages.

Each time you bind two books together the total effort to perform the binding is equal to the number of pages in both books. For example, Binding Book A and Book B will require 512 units of effort.

Write a program that takes in one line of input. The line of input will be the number of pages for each book separated by commas.

Your program must output the minimum units of effort required to bind all the books together.

Input: 100,12,6,40

Output: 234

NB: The best way to bind these books is to firstly bind 12 with 6 which costs 18 units of effort. We now have books of sizes {100, 18, 40}. We then can bind 18 and 40, which costs 58 units of effort. We now have books of sizes {100, 58}. And finally we bind 100 and 58 which requires 158 units of effort. Thus we required 18+58+158 = 234 units of effort.

Input: 900,46,34,187,23,100,2541,3987

Output: 13692

Input: 187,65,13,4,5,89,13,55,4,99,544

Output: 2480