Problem prototype: given a one-dimensional vector, the value of the vector is a positive or negative number, we assume that there is no 0 (there is no such thing as a so-called, just no means), ask which vector value is the biggest? Array Arr [0. ..N] There is SUM (Arr [i] ... arr [j]) is max! where i, J belongs to [0, n].
1. I tried to solve this problem: First, introduce two data structures: a.struct meta {// Record an actionable element int value; // from this location to the next META's start between STARTPOS The value of the vector and the int startPOS; / / The value corresponding to the starting position of the original vector segment.}; B. Struct maxRec {// Record a certain position and value information that may become the maximum value. Int StartPos; int endpos; INT VAL;}; c. Adopt stacks or queues work mode d. Adopt preform data information: - -...... , so that the operable data information is positive and negatively alternately The form, this is conducive to our judgment of data. Of course, the first data or the last data is negative, it is definitely the object we discard, so that the result will be a positive, formatted process between both ends. It is accumulated together with a continuous column number, and eventually makes the above alternating phenomenon. 2. Operation process: We assume that the three values of continuous appearance are O, P, Q. where O, Q is positive, P is the absolute value of the corresponding negative (opposite, because it must be negative).
For the different size relationships of O, P, Q can list the following cases, using corresponding processing methods: AO
0, He is good for Q, thus handling it. The four situations can be summarized as three situations: First. Comprehensive B and D: If o> p, then affirmation, and if p> q, then o Maximum value. II. Comprehensive A and C: If o -------------------------------------------------- -------------------------------------------------- -------------------------------------------------- ------ The problems encountered (can not be seen): 1. Judgment two numbers are a number: A * B <0 is a number, A * b> 0, but multiplication is very No efficiency, you can design the following methods: (a ^ b & 0x80000000) == 0 同号, otherwise a number. Note: & priority is higher than ^, so the above formula should be written: (a ^ b) & 0x8000000000 == 02. The maximum value and the minimum value: any maximum value plus 1 will get the minimum, and the number of digits we usually includes symbolic bits, such as the range of 4-bit integers, is -8 ~ 7, interval is 16 For 4, it is obvious that the maximum positive number is 0111 7. The maximum negative (absolute value) is 0111 1 = 1000, because the first is a symbolic bit, so he is -8, take a positive opposite It is to let the symbol bit to participate in the operation: reflect 1, of course, the maximum number of positive numbers is exactly the minimum negative number, so the absolute value of negative numbers will always be more than the maximum number of positive numbers. -------------- -------------------------------------------------- -------------------------------------------------- -------------------------------------------------- It turns out that my idea is right: I used the time that I (2N) solved this so-called cube. - O (N3) The code has become very simple (Java Description): Public Class Test {INT [] VEC = {31, -41, 59, 26, -153, 58, 97, -93, -23, 84, -43, 108}; // initial array int startPos; // first positive start position Int endpos; // last positive end position / ** * Constructor * / public test () {} / ** * Test function * @Param args * / public static void main (string [] args) {test test = new test (); object [] armeta = test.prepare (TEST.VEC); MaxRec mres = test. Excute (arrmeta); system.out.print (mres);} / ** * Prepare data, write continuous positive or negative numbers * @Param vec * @return * / public object [] prepare (int ] VEC) {ArrayList arrlist = new arraylist (); int CONINT = INTEGER.MIN_VALUE; int sum = 0; // Current accumulation and / * Find the right position * / startpos = 0; endpos = vec.length-1; while (vec [startpos] <0) StartPos ; while (vec [endpos] <0) endpos -; / * Start processing * / Meta ameta = new meta (startpos, 0); for (int i = startpos; i <= endpos; i ) {if (sum == 0 || ((SUM ^ VEC [I]) & conint) == 0) { // That SUM = VEC [I];} else {ameta.value = sum; arrlist.add (ameta); ameta = new meta (i, 0); SUM = 0; I -;}} ameta. Value = sum; // Last data arrlist.add (ameta); return arrlist.toArray ();} / ** * processing process, find the maximum method * @Param arrmeta * / public maxRec Excute (Object [] Arrmeta) {// After our prepare processing, it will inevitably - negative-positive elements arrangement, that is, O> 0, P <0, Q> 0 maxRec MR = New MaxRec (0, 0, 0) Meta O; Meta P; Meta Q; INT i = 0; While (i IF (i 1> = arrmeta.length) {// array crossed processing P = new meta (endpos 1,0);} else {p = (meta) Arrmeta [i 1];} IF (i 2> = arrmeta.length) {// array crossed = new meta (endpos 1,0);} else {q = (meta) Arrmeta [i 2];} // O> P, then affirmation, and if P> q may be maximum. IF (o.value> -p.value) {if (-p.value> = Q.Value && mr.value
