Max Sum Sub Matrix

Given a integer matrix of size m*n. We need to find a sub matrix with the largest sum.

Note:
Negative and Positive numbers are also present.

Solution 1:
List all the Sub Matrices and find the sum of each matrix and then find the maximum sum.

Solution 2:
We construct an output array from the input array in the following manner:
inputArr[m][n] be the input array.
And let us make another array outputArr[m][n] with all fields set to zero by default.
Each element of the array say outputArr[i][j] will store the sum of elements from inputArr[0][0] till inputArr[i][j].

So determine outputArr[i][j] =
inputArr[i][j] + outputArr[i-1][j] + outputArr[i][j-1] - outputArr[i-1][j-1]

Now to find the matrix sum of a matrix starting at i1,j1 till i2,j2 is
sum = outputArr[i2][j2]- outputArr[i1][j2] - outputArr[i2][j1] + outputArr[i1-1][j1-1]

Now we can run an algorithm similar to the first solution only difference is that finding the sum is easier now.

For each sub matrix find the sum and then compare with the maximum sum found till now. Then output the result in the end.

Ideal String

An ideal string is a string where the 1-based index of the first occurrence of each letter is equal to the number of occurrences of that letter in the string. For example, the "BAOOOA" is an ideal string (quotes for clarity only). The letter 'B' appears 1 time, and its index is 1. The letter 'A' occurs 2 times and its first index is 2. The letter 'O' occurs 3 times and its first index is 3.
Given an int length, return the lexicographically smallest ideal string of that length containing only uppercase letters ('A'-'Z'). If there are no such ideal strings of that length, return an empty String instead.
Source: TopCoder
Solution:
To solve this problem we need to come up with a formula which tells us whether it is possible to have such a string at all or not. As we can see that element at index 1 must appear once, index 2 must appear twice and index n must appear n times.

So total length of string = length = 1 + 2 + .... n
hence n*(n+1)/2 = length
We should be able to represent the length as above, if we cannot then empty string can be returned.
If we can represent we should do the following:
1. Find n from the above equation.
2. Fill "A" in the 1st index and fill the remainder(0) of "A" in the n+1 th index.
3. Fill "B" in the 2nd index and fill the remainder(1) of "B" in the index after the previous fill.
3. Fill "C" in the 3rd index and fill the remainder(2) of "C" in the index after the previous fill.
........
n. Fill "n" in the nth index and fill the remainder (n-1) of "n" in the index after previous fill

After the above operation is done, print the array.