我的漫漫程序之旅

专注于JavaWeb开发
随笔 - 39, 文章 - 310, 评论 - 411, 引用 - 0
数据加载中……

一道关于数组的面试题

给定一个数组,当中有正负数,求当中的一段“子数组”(即任意长度,连续的数字),使得这个“子数组”的和是所有“子数组”和中最大的,
如给定的数组为12, -8, 5, 66, -21, 0 ,35, -44,7,则最大的和的子数组为{12, -8, 5, 66, -21, 0 ,35},最大的和为89.

package org.eline.core.utils;

/**
 * 
 * 
@author supercrsky
 * 
 
*/

public class Test
{
    
public void findMax(int s[])
    
{
        
int add[] = new int[100];
        
int k = s[0];
        
int b = 0;// 标记开始位置
        int p = 0;// 标记结束位置
        int i;
        
int j;

        
for (i = 0; i <= s.length; i++)// 整体循环
        {
            
for (j = i; j < s.length; j++)// 子数组循环
            {
                add[i] 
+= s[j];
                
if (add[i] > k)
                
{
                    k 
= add[i];
                    b 
= i;// 获得开始位置下标
                    p = j;// 获得结束位置下标
                }

            }

        }

        System.out.print(
"max sub array:");
        System.out.print(
"{");
        
for (i = b; i <= p; i++)
        
{
            System.out.print(s[i] 
+ " ");
        }

        System.out.println(
"}");
        System.out.print(
"sum:" + k);
    }


    
public static void main(String[] args)
    
{
        
int s[] =
        
101-100100100999-222 - 100100 };
        Test test 
= new Test();
        test.findMax(s);
    }

}



posted on 2008-05-07 17:33 々上善若水々 阅读(1740) 评论(0)  编辑  收藏 所属分类: Java笔试与面试


只有注册用户登录后才能发表评论。


网站导航: